BOJ - 1504번 특별한 최단 경로(C++)

문제 출처: https://www.acmicpc.net/problem/1504

문제 난이도

Gold 4

문제 접근

1번 정점부터 출발해서 중간에 2개의 정점에 무조건 들려야하기 때문에, 두 개의 경우의 수를 따져기만 하면 된다.

• 1->N1->N2->N
• 1->N2->N1->N
  (사실 두번째 경로는 나중에 알게 됨, 문제에서 무방향 그래프라는 조건을 놓쳤다)

처음엔 크루스칼로 접근해서 풀었다가 완전 틀렸다. 왜냐면 다익스트라는 1번부터 각 정점으로 가는 최단 경로를 체크하는 건데 중간 노드를 거쳐야하는 거랑 다르다고 생각했기 때문이다.
그러다 각자 방문할거면 start에서 각 노드로 방문하는 다익스트라가 적합하다는 걸 깨달았다.

통과 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>


using namespace std;

struct info {
	int node, cost;
	info(int n, int c) {
		node = n;
		cost = c;
	}

	bool operator<(const info &d)const {
		return cost > d.cost;
	}
};

vector<info> arr[801];

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

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N, E;
	cin >> N >> E;
	for (int i = 0; i < E; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		arr[a].push_back(info( b,c ));
		arr[b].push_back(info(a, c));
	}

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

	vector<int> d;
	d = dijk(1, N);
	ans1 += d[node1];
	ans2 += d[node2];

	d = dijk(node1, N);
	ans1 += d[node2];
	ans2 += d[N];

	d = dijk(node2, N);
	ans1 += d[N];
	ans2 += d[node1];

	int res = min(ans1, ans2);
	if (res >= 987654321 || res <0) cout << -1;
	else cout << res;
	
	return 0;
}

피드백

계속 98%에서 1초 남기고 틀렸습니다가 떠서 화났다. 하루 후에 다시 풀어보니 res가 완전 -값이 나온다는 걸 알았다.
테스트 케이스
https://www.acmicpc.net/board/view/48805
2 0
1 2

간선이 없고 노드만 있을 때 정점을 제공하는 경우 때문이다. 디버깅을 해보니 MAX값 987654321가 계속 더해지면 int 형 값을 넘어가 완전 음수인 이상한 값이 나온다. 이 경우 처리를 해주고 돌리니 맞았습니다가 떴다.