알고리즘

  • 1 → v1 → v2 → n 과 1 → v2 → v1 → n 중 어느것이 더 짧은지 확인하면 된다.
  • 즉, 원점이 1일때, v1 일때, v2일때 다익스트라를 진행하고, 거기서 나온 거리로 위 거리를 계산하여 출력하면 된다.

코드

#include <iostream>
#include <queue>
#include <vector>
#define INF 2100000000;
 
using namespace std;
 
int n, m, v1,v2, fromOne[801], fromV1[801], fromV2[801];
vector<pair<int, int>> e[801];
priority_queue<pair<int, int>> q;
 
int getAns();
void dijkstra(int* from, int c);
int min(int a, int b) {
	return a < b ? a : b;
}
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
 
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		e[a].push_back({ b, c });
		e[b].push_back({ a, c });
	}
	cin >> v1 >> v2;
 
	cout << getAns();
}
 
int getAns() {
	dijkstra(fromOne, 1);
	dijkstra(fromV1, v1);
	dijkstra(fromV2, v2);
 
	int ans = INF;
	if (fromOne[v1] == ans || fromV1[v2] == ans || fromV1[n] == ans || fromV2[n] == ans)
		return -1;
	return min(fromOne[v1] + fromV1[v2] + fromV2[n], fromOne[v2] + fromV2[v1] + fromV1[n]);
}
 
 
void dijkstra(int* from, int c) {
	for (int i = 1; i <= n; i++)
		from[i] = INF;
	from[c] = 0;
 
	q.push({ 0, c });
	while (!q.empty()) {
		int cost = -q.top().first, cur = q.top().second;
		q.pop();
 
		if (cost > from[cur])
			continue;
 
		for (int i = 0; i < e[cur].size(); i++) {
			int nc = cost + e[cur][i].second, next = e[cur][i].first;
 
			if (nc < from[next]) {
				from[next] = nc;
				q.push({ -nc, next });
			}
		}
	}
}