1238번: 파티

문제 링크

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

1238번: 파티

문제 풀이 코드

#include <iostream>
#include <vector>
#include <queue>
#include <functional>

using namespace std;
using P = pair<int,int>;

const int MN=1010;
const int INF=1e9;

vector <P> graph [MN];
int Dist[MN];
int Answer[MN];

void Dijkstra(int S){
    
    priority_queue<P, vector<P>, greater<P>> pq;
    
    Dist[S]=0;
    pq.push({0,S});

    while(!pq.empty()){
        P cur = pq.top(); pq.pop();
        int w=cur.first;
        int v=cur.second;
        
        if(Dist[v] < w) continue;

        for(int j=0; j<graph[v].size(); j++){
            int next=graph[v][j].first;
            int cost=graph[v][j].second;

            if(Dist[next]>w+cost){
                Dist[next]=w+cost;
                pq.push({Dist[next],next});
            }
        }
    }
} 

int main(void){
    
    int N, M, X; cin>>N>>M>>X;
    
    for(int i=0; i<M; i++){
        int u,v,w; cin>>u>>v>>w;
        graph[u].push_back({v,w});
    }


    //모든 정점에서 X까지 가는 최단 경로를 구함
    for(int i=1; i<=N; i++){
        fill(Dist,Dist+N+1,INF);
        Dijkstra(i);
        Answer[i]=Dist[X];
    }

    fill(Dist,Dist+N+1,INF);
    Dijkstra(X);
    for(int i=1; i<=N; i++){
        Answer[i]+=Dist[i];
    }

    int MAX=-INF;

    for(int i=1; i<=N; i++){
        MAX=max(MAX,Answer[i]);
    }

    cout<<MAX;

    return 0;
}

graph 백터와 우선순위 큐에 가중치와 연결 정점을 저장하는 순서가 달라서 답이 바로 나오지 않았다.

다익스트라를 오는길 가는길 두번 구하는 문제다.