9) 백준 1238 - 파티

1238번: 파티 (acmicpc.net)

1238번: 파티

---

역시나 다익스트라로 풀은 문제긴 한데 메모리나 시간초과 날줄 알았는데 맞춘 문제..

#include <bits/stdc++.h>

using namespace std;

int answer[1001];
int vertex[1001];
int dij[1001];
int rev_dij[1001];

void do_dij(int N, int X, vector<vector<pair<int, int>> > dij) {
	fill_n(vertex, 1001, 100001);
	priority_queue<pair<int, int>> q;
	vertex[X] = 0;
	q.push(make_pair(-vertex[X], X));
	while(!q.empty()) {
		int start_point = q.top().second;
		q.pop();
		for(int i = 0; i < dij[start_point].size(); i++) {
			if(vertex[dij[start_point][i].first] > dij[start_point][i].second + vertex[start_point]) {
				vertex[dij[start_point][i].first] = dij[start_point][i].second + vertex[start_point];
				q.push(make_pair(-vertex[dij[start_point][i].first], dij[start_point][i].first));
			}
		}
	}
	for(int i = 1; i <= N; i++) {
		answer[i] += vertex[i];
	}
	answer[X] = 0;
}

int main(void) {
	fill_n(answer, 1001, 0);
	fill_n(dij, 1001, 10001);
	fill_n(rev_dij, 1001, 10001);
	
	int N, M, X, T, a, b;
	cin >> N >> M >> X;
	
	vector<vector<pair<int, int>> > dij(1001);
	vector<vector<pair<int, int>> > rev_dij(1001);
	
	for(int i = 0; i < M; i++) {
		cin >> a >> b >> T;
		dij[a].push_back(make_pair(b, T));
		rev_dij[b].push_back(make_pair(a, T));
	}
	do_dij(N, X, rev_dij);
	do_dij(N, X, dij);
	
	int max = 0;
	int max_i = 0;
	for(int i = 1; i <= N; i++) {
		if(max < answer[i]) {
			max = answer[i];
			max_i = i;
		}
	}
	cout << max << endl;
}

기본적인 다익스트라를 사용하는데 위 문제의 경우에는 갔다가 돌아오는 경우까지 생각해주어야 한다.

원래 다익스트라 라면 출발 지점이 있다면 다른 도착지들 가는데 각각의 최단거리를 찾아주는 것으로 알고 있다.

그런데 위의 문제 같은 경우에는 도착 지점이 같고 출발 지점이 다 다른 경우를 알아야하기 때문에 조금 생각을 했다.

 

결국 사용한 방법은 완전 뒤집어진 그래프를 하나 더 만드는 것으로 정했다.

(그래프를 하나 더 그려서 메모리 초과 날줄 알았는데..ㅎㅎㅎㅎㅎ)

만약 "1번"에서 "2번"으로 가는 경로가 "3초"의 시간이 걸린다면

뒤집어진 그래프에는 "2번"에서 "1번"으로 가는 경로가 "3초" 라고 저장해준다.

이 두가지의 그래프로 다익스트라를 돌려서 합산만 해주면 끝나는 문제였다.

 

-뿌듯-