백준 1504 특정한최단경로 c++ // 다익스트라 필수경유정점 해결, INF설정방법

https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

1. INF설정방법

-문제 : INF(987654321) *3 > max_int(21억) -> 오버플로우 -> 오답

최악의경우 : 1 ,2, 3, 4, ... 800개의 정점

비용이모두 최대인경우(1000) == 800*1000 ?

그냥 맘편하게 max_int /3(함수호출 최대횟수)으로 설정하는게 편했다..

 

2.의사코드

1~v1~v2~n

1~v2~v1~n 중 최소값이 답이다.

※ go(1,v2) : 1~v2로 가는 모든경로(직진, 여러정점 공유 포함) 중 최소값을 보장함.

 

3. 전체코드

스스로 풀고난후 비교해보니 바킹독님 코드와 100% 일치했다!

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

int n, m, x, st, en,ret,v1,v2;
vector<pair<int, int>> adj[1004];	//adj[1]:{2,3} 1->2로가는비용이 3임
int d[1004], pre[1004]; //시작~해당정점까지 최단거리
int INF = 666666666;

int go(int st, int en) {
	fill(d, d + 1004, INF);
	//{비용, 대상정점}
	priority_queue<pair<int, int>,
		vector<pair<int, int>>,
		greater<pair<int, int>>> pq;
	d[st] = 0;
	pq.push({ d[st],st });
	while (pq.size()) {
		auto cur = pq.top(); pq.pop();
		//2. 해당 거리가 최단거리테이블값과 다르면
		//더짧은경로가 있음 -> 무쓸모 -> pass
		if (d[cur.second] != cur.first) continue;
		//3. 이웃한 정점들에대해 직진보다 현재정점을 거치는게 더 싸면 
		//d갱신, 큐에추가
		for (auto next : adj[cur.second]) {
			if (d[next.second] > d[cur.second] + next.first) {
				d[next.second] = d[cur.second] + next.first;
				pq.push({ d[next.second] ,next.second });
				pre[next.second] = cur.second;
				//경로복원 : (이전정점을 기록만하면된다)
				//pre[next.정점]=cur.정점 
			}
		}
	}
	return d[en];
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);


	cin >> n >> m;
	while (m--) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back({ w,v });
		adj[v].push_back({ w,u }); //양방향
	}
	cin >> v1 >> v2;

	en = n;
	int a= go(1, v1) + go(v1, v2) + go(v2, en);
	int b = go(1, v2) + go(v2, v1) + go(v1, en);
	int ret = min(a, b);

	if (ret >= 666666666) cout << -1;
	else cout << ret;

	return 0;
}