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

 

 

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define F first
#define S second
using namespace std;
typedef pair<int, int> PII;

int V, E, X;
int d1[1001], d2[1001];
vector<PII> go[1001], back[1001], temp[1001];
priority_queue<PII, vector<PII>, greater<PII>> pq;
const int INF = 1e9 + 10;

void dijkstra(vector<pair<int, int>>* g, int* d, int start){
    d[start] = 0;
    pq.push({d[start], start});
    while(!pq.empty()){
        auto cur = pq.top();
        pq.pop();
        if(d[cur.S] != cur.F) continue;
        for(auto nxt : g[cur.S]){
            if(d[nxt.S] > nxt.F + d[cur.S]) {
                d[nxt.S] = nxt.F + d[cur.S];
                pq.push({d[nxt.S], nxt.S});
            }
        }
    }
}

int solve(){
    int ans = 0;
    fill(d1, d1+V+1, INF);
    fill(d2, d2+V+1, INF);
    for(int i=1; i<=V; i++){
        for(int j=0; j<temp[i].size(); j++){
            go[temp[i][j].S].push_back({temp[i][j].F, i});
            back[i].push_back({temp[i][j].F, temp[i][j].S});
        }
    }
    dijkstra(go, d1, X);
    dijkstra(back, d2, X);
    //for(int i=1; i<=V; i++) cout << d1[i] << " ";
    //cout << "\n";
    //for(int i=1; i<=V; i++) cout << d2[i] << " ";
    for(int i=1; i<=V; i++) ans = max(ans, d1[i] + d2[i]);
    return ans;
}

int main(void){
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    cin >> V >> E >> X;
    while(E--){
        int u, v, w;
        cin >> u >> v >> w;
        temp[u].push_back({w, v});
    }
    cout << solve();
    return 0;
}