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

특정한 최단 경로 문제

[풀이]

start, node1, node2, destination이 주어지는 것인데,
start->node1 -> node2 -> destination이 짧은지 아님
start->node2 -> node1 -> destination이 짧은지 확인해야 한다.
그러기 위해서 가중치가 있는 최단 경로 이니 다익스트라를 사용하는 것이 좋을 것이고
위 두 경로를 (start, node1), (node1, node2),(node2, destination)이런식으로 나눠서
구한 후 각각 더해 줘야 할 것 이다.

[코드]

#include <iostream>
#include <vector>
#include <queue>
#define N_MAX 801
#define INF 987654321

using namespace std;

int N, E;
int start = 1;
int destination;
int a, b;
long long answer = INF;
vector<pair<int, long long>> adj[N_MAX];


long long dijkstra(int departure, int desti) {
	long long d[N_MAX] = { INF, };
	fill_n(d, N_MAX, INF);
	priority_queue<pair<int, int>> q;

	d[departure] = 0;
	q.push({ departure, 0 });

	while (!q.empty()) {
		pair<int, long long > cur = q.top();
		q.pop();

		int current = cur.first;
		long long dist = -cur.second;

		if (dist > d[current]) continue;

		for (int i = 0; i < adj[current].size(); i++) {
			int next = adj[current][i].first;
			long long next_dist = adj[current][i].second;

			if (dist + next_dist < d[next]) {
				d[next] = dist + next_dist;
				q.push(make_pair(next, -d[next]));
			}
		}

	}

	return d[desti];


}


int solve() {
	//1 -> node1 -> node2 -> destination
	long long sub_ans = dijkstra(start, a);
	sub_ans += dijkstra(a, b);
	sub_ans += dijkstra(b, destination);
	
	//2 -> node2 -> node1 -> destination
	long long  sub_ans2 = dijkstra(start, b);
	sub_ans2 += dijkstra(b, a);
	sub_ans2 += dijkstra(a, destination);
	
	//위에서 구한 값이 INF보다 크다는 것은 연결되지 않았다는 것
	if (sub_ans >= INF && sub_ans2 >= INF) return -1;
	else if (sub_ans <= sub_ans2) answer = sub_ans;
	else answer = sub_ans2;

	
	return answer;
}

int main() {
	cin >> N >> E;
	int node1, node2, cost;
	for (int e = 0; e < E; e++) {
		cin >> node1 >> node2 >> cost;
		adj[node1].push_back(make_pair(node2, cost));
		adj[node2].push_back(make_pair(node1, cost));
	}
	cin >> a >> b;
	destination = N;

	long long ans = solve();
	cout << ans << "\n";
}

[총평]
다익스트라를 까먹지 않았다면 쉬운....