백준 1504번: 특정한 최단 경로

[문제 링크]

1504번: 특정한 최단 경로

---

문제를 보고 생각난 알고리즘은 플로이드-와샬 알고리즘이었다. 하지만 N이 최대 800이므로 O(N^3)이면 약 5억이 넘게 되어 시간초과가 날 것이라 생각하고 다익스트라 알고리즘으로 구현하였다.

 

정점 v1과 v2를 반드시 지나야 하기 때문에 1부터 N까지 갈 수 있는 방법은 아래 두가지 경로만 가능하다.

경로 1) dist[1][v1] -> dist[v1][v2] -> dist[v2][N] 

경로 2) dist[1][v2] -> dist[v2][v1] -> dist[v1][N]

 

dist[v1][v2] 와 dist[v2][v1] 의 최단경로는 서로 같으므로, 3개의 정점 1, v1, N 을 출발점으로 하는 다익스트라 알고리즘을 수행하여 최단경로를 계산해주면 된다.

---

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

// INF를 987654321로 할 경우
// 62~63 라인에서 int의 최대 범위 넘어갈 수 있다.
const int INF = 700000000;
int N, E;
vector<vector<pair<int, int>>> adj(801);
vector<vector<int>> allDist(801, vector<int>(801, INF));

void dijkstra(int start) {
	vector<int> dist(N + 1, INF);
	dist[start] = 0;

	priority_queue<pair<int, int>> pq;
	pq.push({ 0, start });

	while (!pq.empty()) {
		int here = pq.top().second;
		int cost = -pq.top().first;
		pq.pop();

		if (dist[here] < cost) continue;

		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i].first;
			int nextCost = adj[here][i].second + cost;

			if (dist[there] > nextCost) {
				dist[there] = nextCost;
				pq.push({ -nextCost, there });
			}
		}
	}

	allDist[start] = dist;
}

int main(void) {
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	cin >> N >> E;

	for (int i = 0; i < E; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		adj[a].push_back({ b, c });
		adj[b].push_back({ a, c });
	}

	int v1, v2;
	cin >> v1 >> v2;

	dijkstra(1);
	dijkstra(v1);
	dijkstra(N);

	int path1 = allDist[1][v1] + allDist[v1][v2] + allDist[v2][N];
	int path2 = allDist[1][v2] + allDist[v1][v2] + allDist[v1][N];

	int result = min(path1, path2);

	if (result >= INF)
		cout << -1 << endl;
	else
		cout << result << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 168 day