[baekjoon] 17835

면접보는 승범이네

문제

마포구에는 모든 대학생이 입사를 희망하는 굴지의 대기업 ㈜승범이네 본사가 자리를 잡고 있다. 승범이는 ㈜승범이네의 사장인데, 일을 못 하는 직원들에게 화가 난 나머지 전 직원을 해고하고 신입사원을 뽑으려 한다. 1차 서류전형이 끝난 뒤 합격자들은 면접을 준비하게 되었다.

면접자들은 서로 다른 N개의 도시에 거주한다. 승범이는 면접자들의 편의를 위해 거주 중인 N개 도시 중 K개의 도시에 면접장을 배치했다. 도시끼리는 단방향 도로로 연결되며, 거리는 서로 다를 수 있다. 어떤 두 도시 사이에는 도로가 없을 수도, 여러 개가 있을 수도 있다. 또한 어떤 도시에서든 적어도 하나의 면접장까지 갈 수 있는 경로가 항상 존재한다.

모든 면접자는 본인의 도시에서 출발하여 가장 가까운 면접장으로 찾아갈 예정이다. 즉, 아래에서 언급되는 '면접장까지의 거리'란 그 도시에서 도달 가능한 가장 가까운 면접장까지의 최단 거리를 뜻한다.

속초 출신 승범이는 지방의 서러움을 알기에 각 도시에서 면접장까지의 거리 중, 그 거리가 가장 먼 도시에서 오는 면접자에게 교통비를 주려고 한다.

승범이를 위해 면접장까지의 거리가 가장 먼 도시와 그 거리를 구해보도록 하자.

입력

첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다.

다음 M개의 줄에 걸쳐 한 줄마다 도시의 번호 U, V(U ≠ V)와 도로의 길이 C(1 ≤ C ≤ 100,000)가 공백을 두고 순서대로 주어진다. 이는 도시 U에서 V로 갈 수 있는 도로가 존재하고, 그 거리가 C라는 뜻이다.

마지막 줄에 면접장이 배치된 도시의 번호 K개가 공백을 두고 주어진다.

출력

첫째 줄에 면접장까지 거리가 가장 먼 도시의 번호를 출력한다. 만약 그런 도시가 여러 곳이면 가장 작은 번호를 출력한다.

둘째 줄에 해당 도시에서 면접장까지의 거리를 출력한다.

예제 입력

6 10 2
2 6 2
1 4 1
6 1 5
2 5 1
5 1 4
4 5 6
6 2 3
3 5 1
3 1 1
5 2 2
1 2

예제 출력

4
8

풀이

각 도시별로 면접장까지의 최단거리를 구하려면 다익스트라를 각각 돌려줘야 해서 시간초과가 난다.

그래서 생각한게 면접장에서 출발해서 각도시까지의 거리를 구하는 것이다.

출발지점과 도착지점이 바꿨으니 간선을 입력받을 때 간선도 역방향으로 바꿔줘야 한다.

 

#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

vector<pair<int, int>> *node; // <거리 , 노드>
long long *result;
int *room;
long long INF = 0x7fffffffffffffff;
int v, e, p; // 도시수, 도로수, 면접장

int answerNode;
long long answerDistance = 0;

bool dijkstra(){
    int currentNode, next;
    long long currentDistance, nextDistance;

    for(int i = 0; i < v+1; i++)result[i] = INF;
    
    priority_queue<pair<long long, int>> pq; // dis , node
    for(int i = 0; i < p; i++){
        pq.push(make_pair(0, room[i]));
        result[room[i]] = 0;
    }
    
    
    while(!pq.empty())
    {
        currentNode = pq.top().second;
        currentDistance = -pq.top().first;
        pq.pop();
        
        if(currentDistance > result[currentNode])continue;

        for(int i = 0; i < node[currentNode].size(); i++){
            next = node[currentNode][i].second;
            nextDistance = node[currentNode][i].first + currentDistance;

            if(nextDistance < result[next]){
                result[next] = nextDistance;
                pq.push(make_pair(-nextDistance, next));
            }
        }
    }
    return true;
}

int main(){
    cin.tie(NULL), cout.tie(NULL);
    cin >> v >> e >> p;
    node = new vector<pair<int ,int>>[v+1];
    result = new long long[v+1];
    room = new int[p];

    for(int i = 0; i < e; i++){
        int src, dest, dis;
        cin >> src >> dest >> dis;
        node[dest].push_back(make_pair(dis, src));
    }
    for(int i = 0; i < p; i++){
        cin >> room[i];
    }

    dijkstra();

    for(int i = 0; i < v+1; i++){
        if(answerDistance < result[i] && result[i] != INF){
            answerNode = i;
            answerDistance = result[i];
        }
    }

    cout << "\n" << answerNode << "\n" << answerDistance;
}