파티

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N,M,X;
vector<pair<int,int>> graph[1002]; // 1~1000 사용
vector<int> ans;
int dis[1002];
int back[1002];
// 다익스트라 --> 한 정점에서 나머지 좌표까지 이동하는 최단 거리
void dijkstra(int start){
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    dis[start] = 0;
    pq.push({0, start});
    while(!pq.empty())
    {
        int now = pq.top().second;
        int dist = pq.top().first;
        pq.pop();
        // now까지 현재 최단거리보다 여기까지 온 비용인 dist가 더 크면 최단경로가 아니므로 할 필요가 없다
        // 반드시 dis[now] == dist인 경우만 여기에 오는 것이 아님
        if(dis[now] < dist) continue; 
        for(int i=0;i<graph[now].size();i++)
        {
            int cost = dist + graph[now][i].second;
            if(cost < dis[graph[now][i].first]){
                dis[graph[now][i].first] = cost;
                pq.push({cost, graph[now][i].first});
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> N >> M >> X;
    for(int i=0;i<M;i++)
    {
        int a, b, cost;
        cin >> a >> b >> cost;
        graph[a].push_back({b,cost});
    }
    /* X에서 나머지 좌표까지 가는 최단 거리 구해놓기 */
    fill(dis, dis+1002, 1e9);
    dijkstra(X);
    for(int i=0;i<1002;i++) back[i] = dis[i];
    /* 나머지 좌표에서 X까지 가는 최단거리 구하기 */
    for(int i=1;i<=N;i++)
    {
        if(i == X) continue;
        int cost = 0;
        fill(dis, dis+1002, 1e9);
        dijkstra(i);
        cost += dis[X]; // 가는 시간
        cost += back[i]; // 오는 시간
        ans.push_back(cost);
    }
    sort(ans.begin(), ans.end());
    cout << ans.back();
    return 0;
}

• 핵심
  • 다익스트라(Dijkstra) 알고리즘 사용 : 한 정점에서 모든 정점까지 최단거리 구하기 (O(NlogN))