백준 1238. 파티 (다익스트라)

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

1238번: 파티

1. 특징

1) 다익스트라

 

2. 구현 포인트

1) 마을을 순회하면서, 다익스트라 알고리즘: i마을에서 x마을까지 최단거리를 구하고, 배열에 저장

2) 기본적인 다익스트라 알고리즘: x마을에서 모든 마을까지

 

3. 코드

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

int n, m, x;
vector<pair<int ,int>> adj[1002];
int d[1002]; //최단 거리 테이블
int go[1002]; // x마을로 갈때 최단거리 테이블
int u, v, w;
const int INF = 1e9+10;
int main()
{           
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> x;

    for(int i = 0; i < m; i++)
    {
        cin >> u >> v >> w;
        adj[u].push_back(make_pair(w, v));
    }

    
    //i마을에서 x까지 최단거리
    for(int i = 1; i <= n; i++)
    {
        if(i == x) continue;
        fill(d, d+n+1, INF);
        //거리가 작은수부터 출력
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        d[i] = 0;
        pq.push(make_pair(0, i));
        while(!pq.empty())
        {
            auto cur = pq.top(); pq.pop();
            
            if(d[cur.second]!=cur.first) continue;
            for(auto nxt: adj[cur.second])
            {
                if(d[nxt.second] <= d[cur.second] + nxt.first) continue;
                d[nxt.second] = d[cur.second] + nxt.first;
                pq.push(make_pair(d[nxt.second], nxt.second));
            }
            
        }
        go[i] = d[x];

    }


    //x에서 각 마을로 돌아오는 최단거리
    fill(d+1, d+n+1, INF);

    //거리가 작은수부터 출력
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    d[x] = 0;
    pq.push(make_pair(0, x));

    while(!pq.empty())
    {
        auto cur = pq.top(); pq.pop();
        
        if(d[cur.second]!=cur.first) continue;
        for(auto nxt: adj[cur.second])
        {
            
            if(d[nxt.second] <= d[cur.second] + nxt.first) continue;
            
            d[nxt.second] = d[cur.second] + nxt.first;
            pq.push(make_pair(d[nxt.second], nxt.second));
        }
        
    }


    for(int i = 1; i <= n; i++)
    {
        d[i] = d[i] + go[i];
    }

    cout << *max_element(d+1, d+n+1);



    

}