[백준][C++] 1504: 특정한 최단 경로

문제 링크: https://www.acmicpc.net/problem/1504

 

다익스트라를 여러번 쓰면 되는 문제입니다

그냥 1->v1->v2->N만 구하면 되니까 금방 풀 줄 알았는데 역시나 실수가 있었습니다

• 다익스트라 구현을 잘못함
• 1->v2->v1->N도 있었음

이제 다익스트라 알고리즘 만들면서 할 수 있는 실수는 다 해본 것 같습니다. 이젠 안틀리겠죠..?

아무튼 [1->v1] [v1->v2] [v2->N] / [1->v2] [v2->v1] [v1->N]을 구해서 두 경로 모두 빵꾸가 나있으면 -1, 아니면 둘 중 짧은 경로를 출력하면 됩니다.

양방향 그래프이기 때문에 [v1->v2] == [v2->v1] 입니다. 굳이 두번 구하지 않아도 됩니다

 

#pragma GCC optimize ("Ofast")

#define _CRT_SECURE_NO_WARNINGS
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING

#include <bits/stdc++.h>
using namespace std;


vector<pair<int, int>> adj[800];	// idx, cost
const int INF = 987654321;
int N, E;


int dijkstra(int src, int dest) {
	vector<int> dist(N, INF);
	dist[src] = 0;

	priority_queue<pair<int, int>> pq;	// cost(-), idx
	pq.emplace(0, src);

	while (!pq.empty()) {
		auto [cost, here] = pq.top();
		cost = -cost;
		pq.pop();

		if (dist[here] < cost) continue;

		for (auto& edge : adj[here]) {
			auto there = edge.first;
			auto nextDist = cost + edge.second;

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

	return dist[dest];
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	cin >> N >> E;

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

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


	bool found = true;
	int ans = 0;

	// 1. (1->v1) + (v1->v2) + (v2->N) 
	int d1 = dijkstra(0, v1);
	int d2 = dijkstra(v1, v2);
	int d3 = dijkstra(v2, N - 1);
	if (d1 == INF || d2 == INF || d3 == INF)
		found = false;
	ans = d1 + d2 + d3;


	// 2. (1->v2) + (v2->v1) + (v1->N)
	d1 = dijkstra(0, v2);
	d3 = dijkstra(v1, N - 1);
	if ((d1 == INF || d2 == INF || d3 == INF) && !found)
		found = false;
	ans = min(ans, d1 + d2 + d3);
	

	cout << (found ? ans : -1) << '\n';
	

	return 0;
}