백준 1238번 : 파티

문제 링크 : https://www.acmicpc.net/problem/1238

1238번: 파티

 문제 설명 

 

1. 각 마을에는 한명의 학생이살고 각 마을마다 파티가 열린다.

2. 각 마을로 이동하는 단방향 그래프가 주어짐

3. 학생들이 모든 마을을 다들리고 집에돌아오는 시간이 가장 오래걸리는 학생의 소요 시간 출력. 

 

 알고리즘 

 

1. 각학생(마을) 별로 다익스트라를 돌린다..

2. 마을별로 각 마을을 도는 데 드는 시간을 모두 합하여 최대 값을 출력한다.

 

 코드 

 

#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
 
using namespace std;
typedef pair<int, int> P;
 
int INF = 9867654321;
int N, M, X;
int check[1001][1001];
vector<P> v[1001];
 
void dijkstra(int start) {
    check[start][start] = 0;
    priority_queue<P> pq;
    pq.push(P(0,start));
    while (!pq.empty()) {
        int curr = pq.top().second;
        int dis = -pq.top().first;
        pq.pop();
 
        if (check[start][curr] < dis) {
            continue;
        }
 
        for (int i = 0; i < v[curr].size(); i++) {
            int next = v[curr][i].first;
            int next_dis =dis+ v[curr][i].second;
 
            if (next_dis < check[start][next]) {
                check[start][next] = next_dis;
                pq.push(P(-next_dis, next));
            }
        }
 
    }
 
 
}
 
int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    cin >> N >> M >> X;
 
 
    //간선 입력
    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back(P(b, c));
    }
 
    //배열 초기화
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= N; j++) {
            check[i][j] = INF;
        }
    }
 
    //다익스트라
    for (int i = 1; i <= N; i++) {
        dijkstra(i);
    }
 
    //결과값
    int result = 0;
    for (int i = 1; i <= N; i++) {
        result = max(result, check[i][X] + check[X][i]);
    }
 
    cout << result;
 
 
}