11) 백준 1504 - 특정한 최단 경로

1504번: 특정한 최단 경로 (acmicpc.net)

1504번: 특정한 최단 경로

---

시간 초과나 생각하지 않은 예외가 있어 틀릴줄 알았던 문제

#include <bits/stdc++.h>

using namespace std;

int vertex_1[801]; // v1먼저 가는 경우 
int vertex_2[801]; // v2먼저 가는 경우 
int dij[801];

// 0. DIJ 구현 (3.2) 
// 1. 1에서 V1 또는 V2로 가는 길 찾기
// 2. V1또는 V2에서 V2E또는 V1으로 가는 길 찾기
// 3. V1, V2에서 N으로 가는 길 찾기 
void dijkstra(int start, int end, int vertex[], vector<vector<pair<int, int>> > &dijk) {
	priority_queue<pair<int, int> > q;
	q.push(make_pair(-vertex[start], start));
	
	if(vertex[start] == 999999999) {
		return;
	}
	
	while(!q.empty()) {
		int start_point_vxt = -q.top().first;
		int start_point = q.top().second;
		q.pop();
		if(start_point == end) {
			return;
		}
		for(int i =0; i < dijk[start_point].size(); i++) {
			int target = dijk[start_point][i].first;
			if(vertex[target] > dijk[start_point][i].second + vertex[start_point]) {
				vertex[target] = dijk[start_point][i].second + vertex[start_point];
				q.push(make_pair(-vertex[target], dijk[start_point][i].first));
			}
		}
	}
}

int main(void) {
	int answer = 999999999;
	fill_n(dij, 801, 200001);
	fill_n(vertex_1, 801, 999999999);
	fill_n(vertex_2, 801, 999999999);
	
	vector<vector<pair<int, int>> > dij(801);
	
	int N, E;
	cin >> N >> E;
	
	int a, b, c;
	for(int i = 0; i < E; i++) {
		cin >> a >> b >> c;
		dij[a].push_back(make_pair(b, c));
		dij[b].push_back(make_pair(a, c));
	}
	
	int v1, v2;
	cin >> v1 >> v2;
	
	int reset_v1 = 0;
	int reset_v2 = 0;
	
	vertex_1[1] = reset_v1;
	vertex_2[1] = reset_v2;
	
	dijkstra(1, v1, vertex_1, dij);
	dijkstra(1, v2, vertex_2, dij);
	
	reset_v1 = vertex_1[v1];
	reset_v2 = vertex_2[v2];
	
	fill_n(vertex_1, N+1, 999999999);
	fill_n(vertex_2, N+1, 999999999);
	
	vertex_1[v1] = reset_v1;
	vertex_2[v2] = reset_v2;
	
	dijkstra(v1, v2, vertex_1, dij);
	dijkstra(v2, v1, vertex_2, dij);
	
	reset_v1 = vertex_1[v2];
	reset_v2 = vertex_2[v1];
	
	fill_n(vertex_1, N+1, 999999999);
	fill_n(vertex_2, N+1, 999999999);
	
	vertex_1[v2] = reset_v1;
	vertex_2[v1] = reset_v2;
	
	dijkstra(v2, N, vertex_1, dij);
	dijkstra(v1, N, vertex_2, dij);
	
	if(vertex_1[N] > vertex_2[N]) {
		answer = vertex_2[N];
	}
	else {
		answer = vertex_1[N];
	}
	
	if(answer == 999999999) {
		cout << "-1" << endl;
	}
	else {
		cout << answer << endl;
	}
	
	return 0;
	
}

다익스트라를 사용하였는데 두가지로 생각했다.

1. 1 - v1 - v2 - N (vertex_1)

2. 1 - v2 - v1 - N (vertex_2)

두가지 경로를 사용하고 경유지에 도착하면 리턴을 해주었다.

그리고 경유지의 최단 경로를 따로 저장하고 (reset_v1, reset_v2가 역할을 맡았다.)

fill_n으로 다시 전부 초기화를 시켜준 다음에 경유지에 따로 저장한 경유지의 최단 경로를 다시 넣어주었다.

 

다익스트라 함수가 시작되기 전에 경유지에 "999999999" 값이 들어있다면 경유지에 도착을 못한다는 의미로 바로 return을 시켜준다. 다음에 다시 함수가 시작되도 계속 리턴을 해주어 값이 바뀌지 않는다.

 

마지막에는 두 경로중 더 짧은 경로를 비교하여 answer에 저장을 해주었고 둘다 "999999999"가 나올 경우 도착하지 못한다는 의미로 "-1"이 출력되게 된다.

 

틀릴줄 알았는데 맞춰서 기분이 좋다!  으헤헤