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

방법

다익스트라 알고리즘

1번정점부터 N번정점까지 최단거리 구하기
(단, n1와 n2를 모두 포함)

① 1 -> n1 -> n2 -> N
② 1 -> n2 -> n1 -> N

두 가지 최단거리 중, 더 작은 값이 정답
(n1 -> n2와 n2 -> n1는 양방향이므로 같은 최단거리이므로 총 5번의 다익스트라)

주의사항

INF값을 3번 더해주는 과정에서 오류 발생 (92%에서 계속 틀렸습니다)
매번 다익스트라 돌릴 때마다 INF값인지 확인 후에 더하기

코드

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

struct info {
	int n, w;
	info() {};
	info(int n, int w) :n(n), w(w) {};

	bool operator<(const info i)const {
		return w > i.w;
	}
};

int N, E, n1, n2;
vector<info> g[810];
int dist[810];
bool check[810];

int dijkstra(int start, int end) {
	for (int i = 0; i <= N; i++) { // memset은 0이나 -1로 초기화할 때 사용
		dist[i] = INF;
		check[i] = false;
	}
	priority_queue<info> pq;
	pq.push(info(start, 0));
	dist[start] = 0;
	while (!pq.empty()) {
		info cur = pq.top();
		pq.pop();
		if (check[cur.n]) continue;
		check[cur.n] = true;
		for (int i = 0; i < g[cur.n].size(); i++) {
			int nxt_n = g[cur.n][i].n;
			int nxt_w = g[cur.n][i].w;
			if (dist[nxt_n] > dist[cur.n] + nxt_w) {
				dist[nxt_n] = dist[cur.n] + nxt_w;
				pq.push(info(nxt_n, dist[nxt_n]));
			}
		}
	}
	if (dist[end] == INF) return -1;
	else return dist[end];
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> E;
	for (int i = 0, u, v, w; i < E; i++) {
		cin >> u >> v >> w;
		g[u].push_back(info(v, w));
		g[v].push_back(info(u, w));
	}
	cin >> n1 >> n2;
	// 1->n1->n2->N
	// 1->n2->n1->N
	int path11 = dijkstra(1, n1);
	int path12 = dijkstra(n1, n2);
	int path13 = dijkstra(n2, N);
	int path21 = dijkstra(1, n2);
	int path22 = path12;
	int path23 = dijkstra(n1, N);

	// INF를 3번 더해줘서 계속 오류 -> 더하기 전에 미리 오류처리
	if (path11 == -1 || path12 == -1 || path13 == -1 || path21 == -1 || path23 == -1) {
		cout << -1;
	}
	else {
		cout << min(path11 + path12 + path13, path21 + path22 + path23);
	}

	return 0;
}