파티 (feat. 백준, 1238번)

파티
https://www.acmicpc.net/problem/1238

1238번: 파티

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
int N, M, X;
set<pair<int, int>> arr[1001];
int ans[1001];
struct cmp{
	bool operator()(const pair<int, int>& v1, const pair<int, int>& v2) const{
		if(v1.first == v2.first)
			return v1.second > v2.second;
		return v1.first > v2.first;
	}
};
int bfs(register int s, register int e) {
	if(s == e)
		return 0;
    for(register int n = 1; n <= N; ++n)
        ans[n] = 999999999;
	register int p1, p2, t1, t2;
	ans[s] = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> q;
	q.push(make_pair(0, s));
	while (!q.empty()) {
		auto v = q.top(); q.pop();
		t1 = v.first, p1 = v.second;
        if(p1 == e)
            continue;
		for (auto iter = arr[p1].begin(); iter != arr[p1].end(); ++iter) {
			p2 = iter->first, t2 = iter->second;
			if (ans[p2] > t1 + t2)
				ans[p2] = t1 + t2, q.push(make_pair(ans[p2], p2));
		}
	}
    return ans[e];
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	cin >> N >> M >> X;
    for(register int m = 1, x, y, t; m <= M; ++m)
        cin >> x >> y >> t, arr[x].insert(make_pair(y, t));
    register int time = 0;
    for(register int n = 1; n <= N; ++n)
        time = max(time, bfs(n, X) + bfs(X, n));
    cout << time;
	return 0;
}
// *&)*@*

 

반응형

1. 다익스트라 알고리즘을 사용하였습니다.
2. S부터 E까지 간다고 할때, 결국 S부터 X까지 + X부터 S까지 의 값이 가장 큰 수를 구하면 됩니다.
3. 다만 A부터 B까지 갈때는 최단거리로 간다는 전제로 구해야 합니다.
4. 즉, A부터 B까지 갈 수 있는 최단거리를 구하는 방법 (다익스트라) 을 알면 쉽게 풀이할 수 있습니다.