[BOJ] 특별한 최단 경로

[BOJ] 특별한 최단 경로

Problem URL : 특별한 최단 경로

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#define p pair<int,int>
#define MAX_INTEGER 987654321

using namespace std;

vector<p> edge[801];
int N, E;

vector<int> dijk(int start) {
	vector<int> dist(N + 1, MAX_INTEGER);
	dist[start] = 0;
	priority_queue<p> q;
	q.push({ start, 0 });

	while (!q.empty()) {
		int node = q.top().first;
		int cost = q.top().second;
		q.pop();
		if (dist[node] < cost) continue;
		for (int i = 0; i < edge[node].size(); i++) {
			int nextNode = edge[node][i].first;
			int nextCost = edge[node][i].second;
			if (dist[nextNode] > dist[node] + nextCost) {
				dist[nextNode] = dist[node] + nextCost;
				q.push({ nextNode, dist[nextNode] });
			}
		}
	}
	return dist;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> N >> E;
	for (int i = 0; i < E; i++) {
		int node1, node2, cost;
		cin >> node1 >> node2 >> cost;
		edge[node1].push_back({ node2, cost });
		edge[node2].push_back({ node1, cost });
	}

	int node1, node2;
	long long ans1 = 0, ans2 = 0;
	cin >> node1 >> node2;

	vector<int> dist;
	dist = dijk(1); // 1부터 각 노드까지 최단거리 리스트
	ans1 += dist[node1];
	ans2 += dist[node2];

	dist = dijk(node1); // node1부터 각 노드까지 최단거리 리스트
	ans1 += dist[node2];
	ans2 += dist[N];

	dist = dijk(node2); // node2부터 각 노드까지 최단거리 리스트
	ans1 += dist[N];
	ans2 += dist[node1];

	long long res = min(ans1, ans2);
	if (res >= MAX_INTEGER) {
		cout << -1;
	} else {
		cout << res;
	}

	return 0;
}