[백준] 1504번 특정한 최단 경로 C++코드

코드

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>

using namespace std;
typedef long long ll;
const ll INF = 987654321;
ll n, e, a, b, c, vo, vt, visited[808], res;
vector<pair<ll,ll>> adj[808];

ll dijkstra(ll s, ll e) {
	fill(visited, visited + 808, INF);
	priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
	pq.push(make_pair(0, s));
	visited[s] = 0;
	while(!pq.empty()) {
		int dist = pq.top().first;
		int here = pq.top().second;
		pq.pop();
		if(here == e) return visited[here];
		if(visited[here] < dist) continue;
		for(pair<ll,ll> pa : adj[here]) {
			ll cost = dist + pa.second;
			if(cost <= visited[pa.first]) {
				visited[pa.first] = cost;
				pq.push(make_pair(cost, pa.first));
			}
		}
	}
	return INF;
}

int main() {
	cin >> n >> e;
	for(int i = 0; i < e; i++) {
		cin >> a >> b >> c;
		adj[a].push_back(make_pair(b, c));
		adj[b].push_back(make_pair(a, c));
	}
	cin >> vo >> vt;
    // 1 -> v1 -> v2 -> n
	ll reso = dijkstra(1, vo) + dijkstra(vo, vt) + dijkstra(vt, n);
	// 1 -> v2 -> v1 -> n
    ll rest = dijkstra(1, vt) + dijkstra(vt, vo) + dijkstra(vo, n);
	res = min(reso, rest);
    // 길이 없는 경우
	if(res >= INF) res = -1;
	cout << res << '\n';
	return 0;
}

풀이

길에 가중치가 있고 가중치는 음수가 아니기 때문에 다익스트라 알고리즘을 채택했다. 특정한 두 정점을 통과하여 1에서 n으로 가려면 2가지 케이스가 있다.

 

1 -> v1 -> v2 -> n

1 -> v2 -> v1 -> n

 

문제의 조건에 한 번 이동했던 정점은 물론 이동했던 간선도 다시 이동할 수 있다고 되어 있다. 따라서 각각의 경우에 최단경로를 찾아서 더해주면 두 정점을 반드시 거치면서 1번에서 n번으로 가는 최단 경로를 찾을 수 있다.