[그래프] FIRETRUCKS 소방차

1. 문제

 

이 문제는 여러 소방서에서 불난집까지 가는 최단 거리들을 찾는 것이다.

 

이것은 불난집을 여러번 다익스트라를 돌려서 가장짧은 소방서를 찾으면 해결되지만

 

이 문제의 의도는 아니다.

 

(소방서를 기준으로 돌리거나 플로이드의 모든 쌍 최단 경로 알고리즘(O(V^3))을 이용하여 풀 수 도 있지만 느리다)

 

 

 

2. 모든 소방서를 하나로 

 

이 문제는 모든 소방서를 한 소방서에 합치면 다익스트라 한번에  해결 할 수 있다.

 

다음은

 

모든 입력이 주어지고나서 첫번째 소방서에다가 하나로 합친 그래프를 만들고 문제를 해결하는 코드이다.

 

책에서는 인덱스 0 인 임의의 정점을 만들어서 이를 가중치가 0 으로 소방서를 전부 이었다.

 

이렇게하면 모든 소방서에서 동시에 다익스트라를 수행하는것과 같다.

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
 
using namespace std;
 
vector<vector<int> > adj;
vector<int> fire;
vector<int> office;
int V, n, m, E;
 
vector<int> fireOffice(int src)
{
    vector<int> d = vector<int>(V, INT32_MAX);
    priority_queue<pair<int, int> > pq;
    pq.push(make_pair(0, src));
    d[src] = 0;
 
    while(!pq.empty())
    {
        int dist = -pq.top().first;
        int here = pq.top().second;
        pq.pop();
        if(dist > d[here]) continue;
 
        for(int i = 0; i < V; i++)
        {
            if(adj[here][i] == INT32_MAX) continue;
            int there = i;
            int nextDist = adj[here][i] +  dist;
            if(nextDist < d[there])
            {
                d[there] = nextDist;
                pq.push(make_pair(-d[there], there));
            }
        }
    }
    return d;
}
 
void mergeOffice()
{
    int start = office[0];
    for(int i = 1; i < m; i++)
    {
        for(int j = 0; j < V ; j++)
        {
            int a = office[i];
            if(adj[a][j] == INT32_MAX) continue; 
            adj[j][a] = INT32_MAX;
            if(adj[start][j] < adj[a][j]) continue;
            adj[j][start] = adj[a][j];
            adj[start][j] = adj[a][j];
            adj[a][j] = INT32_MAX;
        }
    }
}
 
int main()
{
    int C;
    cin>>C;
    while(C--)
    {
 
        cin>>V>>E>>n>>m;
        adj = vector<vector<int> > (V, vector<int>(V, INT32_MAX));
        fire.clear();
        office.clear();
 
        for(int i = 0 ; i < E; i++)
        {
            int a, b, t;
            cin>>a>>b>>t;
            adj[a-1][b-1] = t;
            adj[b-1][a-1] = t;
        }
        for(int i = 0 ; i < n ; i++) {
            int tmp;
            cin>>tmp;
            fire.push_back(tmp-1);
        }
        for(int i = 0 ; i < m ; i++) {
            int tmp;
            cin>>tmp;
            office.push_back(tmp-1);
        }
        mergeOffice();
 
        int ret = 0;
        vector<int> d = fireOffice(office[0]);
        for(int i = 0; i < n; i++)
        {
            ret += d[fire[i]];
        }
        cout<<ret<<"\n";
 
    }
}
 

FIRETRUCKS