[백준] 1238번 파티

1238 파티

문제

---

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

입력

---

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

출력

---

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

---

풀이)

최단시간을 구하는 문제이므로 dijkstra나 floyd를 이용해서 풀면 되는 문제이다.

주의할 점은 도로들이 단방향이다보니, X마을까지 갔다 오는 길이 다를 수도 있다.

따라서,

i번 학생이 X마을을 왕복하는 최소시간 = i → X 로 가는 최소시간 + X → i 로가는 최소시간 이다.

나같은 경우는 dijkstra로 X마을에서 각 학생까지 가는데 최소시간을 구해놓고,

for문으로 각 학생들마다 dijkstra를 돌려 X마을까지 가는 최소시간을 구해 둘을 더했다.

((이렇게 한사람씩 Dijkstra를 하는 방법도 있지만, 어차피 모든 학생들을 다 확인해봐야하니깐

Floyd로 푸는 것도 좋은 방법이다.))

코드)

#include <stdio.h>
#include <vector>
#include <queue>
using namespace    std;
 
int n;//마을 개수 겸 학생 수
vector <pair<int, int>> adj[1001]; //그 마을에서 연결되있는 <다른 마을.비용>
int INF = 999999999;
 
vector <int> Dijkstra(int start) {
    vector <int> dist(n+1,INF); //<최단거리>
    priority_queue <pair<int, int>> qu; //<최소비용,정점>
 
    dist[start] = 0;//자기자신은 0
    qu.push({ 0,start });
 
    while (!qu.empty()) {
        int here, cost;
        cost = -qu.top().first;
        here = qu.top().second;
        qu.pop();
        if (dist[here] < cost) continue;
        for (int i = 0; i < adj[here].size(); i++) {
            int next = adj[here][i].first;
            int nextdis = adj[here][i].second + cost;
 
            if (dist[next] > nextdis) {
                dist[next] = nextdis;
                qu.push({ -nextdis,next });
            }
        
        }
    }
    return dist;
}
 
int main() {
    int m, x; //간선 수, 파티열리는 마을 위치
    scanf("%d %d %d", &n, &m, &x);
    for (int i = 0; i < m; i++) {
        int start, end, cost;
        scanf("%d %d %d", &start, &end, &cost);
        adj[start].push_back(make_pair(end, cost));
    }
    
    int maxtime = 0;
 
    vector <int> party = Dijkstra(x);//파티 연 마을에서 각자 마을까지
    for (int i = 1; i <= n; i++) {
        if (i == x) continue;//본인 마을에서 파티열경우
        vector <int> check = Dijkstra(i); //i번 마을에서 파티연곳을 가는것
        int time = check[x] + party[i];//갔다오는데 걸린시간
        if (maxtime < time) {
            maxtime = time;
        }
    }
 
    printf("%d", maxtime);
    return 0;
}