백준 알고리즘 1504 (특정한 최단 경로) - C++, Python

[문제] 백준 알고리즘 1504 (특정한 최단 경로)

> https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

 

정점 N개, 간선 E개가 주어지고, E개의 줄에 걸쳐 a, b, c가 주어진다.

그리고 두 개의 지나야할 정점이 주어진다.

1 -> 두 정점 -> N으로 이동하는 데에 최단 거리를 구하는 문제이다.

만약, 경로가 없으면 -1을 출력한다.

 

첫번째 경로는 1->정점1->정점2->N, 두번째 경로는 1->정점2->정점1->N

두 가지 경우가 있으므로, 두 경로 중에 최단 거리를 고르면 된다.

 

첫번째 경로의 최단 거리로 설명하면,

1 -> 정점1의 최단 + 정점1 -> 정점2의 최단 + 정점2 -> N의 최단 거리를

구해서 동일한 방식으로 두번째 경로의 최단 거리와 비교한다.

그 두 경로 중에 작은 경로를 출력하고, 다익스트라 알고리즘을 쓰기 때문에

경로가 존재하지 않는다면 INF(1e9 설정)보다 클 것이므로, 이 때 -1을 출력한다.

 

[C++]

#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
const int MAX = 801;
const int INF = 1e9;
vector< pair<int, int> > graph[MAX];
int n, e;
int must1, must2;

int solve_bfs(int start, int arrive) {
	priority_queue< pair<int, int> > pq;
	vector<int> dijk(n + 1, INF);
	pq.push({ 0, start });
	dijk[start] = 0;

	while (!pq.empty()) {
		int w = pq.top().first;
		int v = pq.top().second;
		pq.pop();
		if (dijk[v] < w) {
			continue;
		}
		for (int i = 0; i < graph[v].size(); i++) {
			int nw = graph[v][i].first;
			int nv = graph[v][i].second;
			nw = nw + w;
			if (dijk[nv] > nw) {
				dijk[nv] = nw;
				pq.push({ nw, nv });
			}
		}
	}
	return dijk[arrive];
}

int main() {
	scanf("%d %d", &n, &e);
	for (int i = 0; i < e; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		graph[a].push_back({ c, b });
		graph[b].push_back({ c, a });
	}
	scanf("%d %d", &must1, &must2);
	int p1 = solve_bfs(1, must1) + solve_bfs(must1, must2) + solve_bfs(must2, n);
	int p2 = solve_bfs(1, must2) + solve_bfs(must2, must1) + solve_bfs(must1, n);

	if (p1 < INF && p1 < p2 ) {
		printf("%d\n", p1);
	}
	else if (p2 < INF && p2 < p1) {
		printf("%d\n", p2);
	}
	else {
		printf("-1\n");
	}
	return 0;
}

 

[Python]

import sys
from heapq import heappush, heappop
n, e = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
for _ in range(e):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a].append([c, b])
    graph[b].append([c, a])

must1, must2 = map(int, sys.stdin.readline().split())

def solve_bfs(start, arrive):
    queue = []
    dijk = [1e9] * (n + 1)
    queue.append((0, start))
    dijk[start] = 0
    while queue:
        w, v = heappop(queue)
        if dijk[v] < w:
            continue
        for nw, nv in graph[v]:
            nw += w
            if dijk[nv] > nw:
                dijk[nv] = nw
                heappush(queue, (nw, nv))
    return dijk[arrive]

p1 = solve_bfs(1, must1) + solve_bfs(must1, must2) + solve_bfs(must2, n)
p2 = solve_bfs(1, must2) + solve_bfs(must2, must1) + solve_bfs(must1, n)
if p1 > 1e9 and p2 > 1e9:
    print(-1)
else:
    print(min(p1, p2))