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 }); } } }}