[백준/BOJ] 1238번 파티 (C++)

www.acmicpc.net/problem/1238

1238번: 파티

다익스트라 알고리즘을 이용하면 해결할 수 있는 문제 (다시 풀기)

 

새롭게 알게된 점

pair형에서 sort함수를 쓰면 first를 기준으로 적용된다. (default)

 

다익스트라를 이용해 1번부터 n번 정점까지 target으로 갈 수 있는 최소 비용을 dist배열에 갱신한 후, res배열에 복사합니다. dist배열을 초기화하고, 이번에는 target에서 1번부터 n번 정점까지 갈 수 있는 최소 비용을 dist배열에 갱신하고 이를 기존의 res배열에 더해줍니다. 마지막으로 res배열의 최대값을 출력해줍니다. 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int n, m, target, answer = -2147000000;
vector<pair<int, int > > graph[1001];
int dist[1001], res[1001];

void init() {
	for(int i = 1; i <= n; i++) {
		dist[i] = 2147000000;
	}
}

void D(int start) {
    priority_queue<pair<int, int >, vector<pair<int, int > >, greater<pair<int, int > > > pq;
    pq.push({ 0, start });
    dist[start] = 0;
    while(!pq.empty()) {
        auto now = pq.top();
        int v = now.second;
        int e = now.first;
        pq.pop();
        if(dist[v] < e) continue;

        for(int i = 0; i < graph[v].size(); i++) {
            int next = graph[v][i].first;
            int nextVal = e + graph[v][i].second;
            if (dist[next] > nextVal) {
                dist[next] = nextVal;
                pq.push({ nextVal, next });
            }
        }
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> target;

    while(m--) {
        int x, y, w;
        cin >> x >> y >> w;
        graph[x].push_back({ y, w });
    }

    for(int i = 1; i <= n; i++) {
        init();
        D(i);
        res[i] = dist[target];
    }
    
    init();
    D(target);
    for(int i = 1; i <= n; i++) {
    	res[i] += dist[i];
    	answer = max(answer, res[i]);
	}
    
    cout << answer;
}