백준 1504

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

1504번: 특정한 최단 경로

이 문제의 겨우  testcase는 다맞게 나오는데 이상하게 계속 틀렸다고 나왔다. 이에 계속 틀린이유를 찾느라 시간을 많이 소비했다

일단 이문제의 경우 2가지의 경우를 생각해주어야한다

시작점-V1-V2-종점

시작점-V2-V1-종점

여기서 문제에서 시작점에서 V1-V2를 경우하여 종점을 가는것이기에 종점 부터 가는 경우의 수는 생각 해 줄 필요가 없다.

당연히 Vertext와 Edge에 관한 문제이기에 익숙한 다익스트라를 활용했다.

#include <iostream>
#include <queue>
#include <vector>
#include<algorithm>
#define INT_MAX 987654321
using namespace std;
int N, E;
priority_queue < pair<int, int>, vector<pair<int, int>>, greater <pair<int, int>>> djikstra_pq;
vector<pair<int, int>> djikstra_v[801];
vector<int> distanceV(801);
void djikstra(int i) {
	int start = i;
	int toCost = 0;
	djikstra_pq.push({ toCost,start });
	distanceV[start] = 0;
	while (!djikstra_pq.empty()) {
		int toCost = djikstra_pq.top().first;
		int toVertex = djikstra_pq.top().second;
		
		djikstra_pq.pop();
		int distanceToNextVertex = distanceV[toVertex];
		if (distanceToNextVertex < toCost) {
			continue;
		}
		for (int i = 0; i < djikstra_v[toVertex].size(); i++) {
			int cost = djikstra_v[toVertex][i].first + toCost;
			int nextIdx = djikstra_v[toVertex][i].second;
			if (cost < distanceV[nextIdx]) {
				distanceV[nextIdx] = cost;
				djikstra_pq.push({ cost,nextIdx });
			}
		}
		
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> E;
	for (int i = 0; i < E; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		djikstra_v[a].push_back({ c,b });
		djikstra_v[b].push_back({ c,a });
	}
	int v1, v2;
	cin >> v1 >> v2;
	int sToV1, sToV2, v1ToV2, v1ToN, v2ToN;
	distanceV.assign(N+1, INT_MAX);
	djikstra(1);
	sToV1 = distanceV[v1];
	sToV2 = distanceV[v2];
	distanceV.assign(N+1, INT_MAX);
	djikstra(v1);
	v1ToV2 = distanceV[v2];
	v1ToN = distanceV[N];
	distanceV.assign(N+1, INT_MAX);
	djikstra(v2);
	v2ToN = distanceV[N];

	int ans = INT_MAX;

	ans = min(ans, sToV1 + v1ToV2 + v2ToN);
	ans = min(ans, sToV2 + v1ToV2 + v1ToN);

	if ((v1ToV2 == INT_MAX)||ans==INT_MAX) {
		cout << -1;
	}
	else {
		cout << ans;
	}
}

내가 이렇게 작성한 코드에서 climits에 INT_MAX를 사용하면 오류가 났다 아마도 테스트케이스중 지나가지 않은 경로에대한 값을 출력할 때 climits에 INT_MAX를 사용하면 값이 오바되면서 최종출력값에 오류가 날것으로 추측했다 이에 Vertex의 최대갯수 800 그리고 가중치의 최대갯수 1000 그리고 구간을 3개로 나누었기에 3을곱한값보다 크지만 INT_MAX보다 작은 값을 최대값으로 지정해주고 풀었다

테스트케이스가 맞을 때 틀렸습니다가 계속 나올 경우 이부분도 생각해서 풀면 좋을거 같다