소방차 (FIRETRUCKS)

algospot.com :: FIRETRUCKS

다익스트라

 

문제 설명

 

각 소방서마다 불이나는 집까지의 최단거리를 구하고, 그 중에서 가장 가까운 소방서만 선택해서 전체 시간을 구한다면 시간초과가 날 것이다.

 

Key point는 소방서가 시작점이기 때문에 가상의 정점(0번 정점)을 만들고, 0번 정점에서 소방서까지 가는 비용을 0으로 잡고 queue에 넣어주면 된다!

-> 0번 정점에서 모든 소방서로 가중치가 0인 간선을 연결한다고 생각하자

 

우선순위 큐에서 항상 가장 적은 시간이 소요되는 간선을 다음 간선으로 선택해 주기 때문에

임의의 정점(V)까지 가는 거리는 여러개의 시작점들 중 특정한 점에서 시작해 V에 도착할 수 있는 최소 시간을 가지게 된다.

즉 모든 위치에 대해서 임의의 소방서로부터의 최단 거리를 얻을 수 있다.

 

 

코드

#include <iostream>
#include <vector>
#include <queue>
 
#define pii pair<int, int>
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
 
const int INF = 1e9+7;
int V, E, n, m;
vector<vector<pii > > Map;
vector<int> firehouse, dist;
 
void input(){
    int a, b, t;
    cin >> V >> E >> n >> m;
    
    Map = vector<vector<pii > >(V + 1);
    firehouse = vector<int>();
    dist.clear();
    dist.resize(V+1, INF);
    
    for(int i = 0; i < E; i++){
        cin >> a >> b >> t;
        Map[a].push_back({t, b});
        Map[b].push_back({t, a});
    }
    for(int i = 0; i < n; i++){
        cin >> a;
        firehouse.push_back(a);
    }
    for(int i = 0; i < m; i++){
        cin >> a;
        Map[0].push_back({0, a});
    }
}
 
void Dijkstra(){
    priority_queue<pii, vector<pii >, greater<pii > > que;
    
    dist[0] = 0;
    que.push({0, 0});
    
    while(!que.empty()){
        int now = que.top().second;
        int min_cost = que.top().first;
        que.pop();
        
        if(min_cost > dist[now]) continue;
 
        for(int i = 0; i < Map[now].size(); i++){
            int next = Map[now][i].second;
            int next_cost = min_cost + Map[now][i].first;
            
            if(next_cost < dist[next]){
                dist[next] = next_cost;
                que.push({next_cost, next});
            }
        }
    }
    
    int res = 0;
    for(int i = 0; i < firehouse.size(); i++){
        res += dist[firehouse[i]];
    }
    cout << res << "\n";
}
 
int main(){
    fastio
    int test;
    cin >> test;
    while(test--){
        input();
        Dijkstra();
    }
    
    return 0;
}