scpc2016_pre1_4.cpp

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

using namespace std;
#define ll long long

const ll INF = LLONG_MAX;
int N, M, K;

int main(){
    setbuf(stdout, NULL);
    int T;
    scanf("%d", &T);
    for(int t =1;  t <= T; t++){
        scanf("%d%d%d", &N, &M, &K);
        vector<vector<pair<int ,int > > > graph;
        graph.resize(N+1);
        for(int i =1 ; i <= M ; i++){
            int a, b, w;
            scanf("%d%d%d", &a, &b, &w);;
            graph[a].push_back(make_pair(b,w));
            graph[b].push_back(make_pair(a,w));
        }
        
        vector<ll> dis(N+1, INF);
        vector<int> from(N+1, 0);
        
        priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > que;
        
        for(int i = 1; i<= K; i++){
            int tmp;
            scanf("%d", &tmp);
            //출발점을 여러 개(대피소 전체)로 설정
            dis[tmp] = 0;
            from[tmp] = tmp;
            que.push(make_pair(0, tmp));
        }
        
        //다익스트라 알고리즘 수행
        while(!que.empty()){
            int now = que.top().second;
            
            que.pop();
            
            for(int i = 0 ; i < graph[now].size(); i++){
                int next = graph[now][i].first;
                int nextDis = graph[now][i].second;
                
                if(dis[next] > dis[now]+nextDis){
                    dis[next] = dis[now]+nextDis;
                    from[next] = from[now];
                    que.push(make_pair(dis[next], next));
                }else if(dis[next] == dis[now]+nextDis){
                    //거리가 같을 경우 번호가 더 작은 대피소로 대피하기 위함
                    if(from[next] > from[now]){
                        from[next] = from[now];
                        que.push(make_pair(dis[next], next));
                    }
                }
            }
        }
        
        ll sumDis = 0, sumN = 0;
        for(int i = 1; i<= N; i++){
            sumDis += dis[i];
            sumN += from[i];
        }
        
        printf("Case #%d\n%lld\n%lld\n", t, sumDis, sumN);
    }
    return 0;
}