소방차 FIRETRUCKS

문제 : https://algospot.com/judge/problem/read/FIRETRUCKS

문제

한겨울 날씨가 추워지면 각종 난방 기구 때문에 화재가 발생하기 쉽습니다. 어느 추운 겨울날 서울 시내 n개의 지역에 동시에 화재가 발생했습니다. 피해를 최소화하기 위해 가능한 한 빠르게 소방차를 파견해야 합니다. 서울 시내에는 m개의 소방서가 있습니다. 화재 장소에서 가장 가까운 소방서에서 소방차를 보낸다고 할 때, 각 화재 장소에 소방차가 도달하기까지 걸리는 시간의 합을 계산하는 프로그램을 작성하세요. 각 소방서에는 소방차가 충분히 많습니다.

이 문제에서 서울 시내는 1부터 V까지 번호 붙여진 V개의 장소들과 이들을 연결하는 E개의 양방향 도로로 구성됩니다. 모든 도로에 대해 도로가 연결하는 두 장소의 번호와 각 도로별 통행 소요 시간이 주어집니다.

예제 지도를 봅시다. 사각형으로 표시된 지점들은 소방서를, 음영으로 칠해진 지점들은 불이 난 지점을 나타냅니다. 2번과 5번 장소에서는 6번 소방서가 가장 가깝고, 3번 장소에서는 4번 소방서가 가장 가깝습니다. 이때, 각 장소에 소방차가 도착하기까지 걸리는 시간은 2번 장소에 8분, 5번 장소에 4분, 3번 장소에 4분으로 총 합은 16분이 됩니다.

코드 ( C ++ ) 종만북 참조

#include <iostream>

#include <string>

#include <algorithm>

#include <cstring>

#include <vector>

#include <queue>

using namespace std;

int V, E, n, m;

vector<vector<pair<int, int>>> adj;

int fire[1002], location[1002];

const int INF = 987654321;

// 우선순위 큐를 사용하지 않은 다익스트라 알고리즘

vector<int> dijkstra(int x)

{

vector<int> dist(V+1, INF);

vector<bool> visited(V+1, false);

dist[x] = 0, visited[x] = false;

while (true) {

int closest = INF, here;

for (int i = 0; i < V+1; ++i)

if (!visited[i] && dist[i] < closest) {

closest = dist[i];

here = i;

}

if (closest == INF) break;

visited[here] = true;

for (int i = 0; i < adj[here].size(); ++i)

{

int there = adj[here][i].first;

if (visited[there]) continue;

int nextDist = dist[here] + adj[here][i].second;

dist[there] = min(dist[there], nextDist);

}

}

return dist;

}

// 우선순위 큐를 사용한 다익스트라 알고리즘

vector<int> dijkstra2(int x)

{

vector<int> dist(V + 1, INF);

dist[x] = 0;

priority_queue<pair<int, int>> pq;

pq.push(make_pair(0, x));

while (!pq.empty()) {

int cost = -pq.top().first;

int here = pq.top().second;

pq.pop();

if (dist[here] < cost) continue;

for (int i = 0; i < adj[here].size(); ++i)

{

int there = adj[here][i].first;

int nextDist = cost +adj[here][i].second;

if (dist[there] > nextDist) {

dist[there] = nextDist;

pq.push(make_pair(-nextDist, there));

}

}

}

return dist;

}

int main()

{

int C;

cin >> C;

while (C--) {

cin >> V >> E >> n >> m;

adj = vector<vector<pair<int, int>>>(E, vector<pair<int, int>>());

for (int i = 0; i < E; ++i)

{

int n1, n2, n3;

cin >> n1 >> n2 >> n3;

adj[n1].push_back(make_pair(n2, n3));

adj[n2].push_back(make_pair(n1, n3));

}

for (int i = 0; i < n; ++i)

cin >> fire[i];

for (int i = 0; i < m; ++i) {

int num;

cin >> num;

adj[0].push_back(make_pair(num, 0));

adj[num].push_back(make_pair(0, 0));

}

vector<int> dist;

dist = dijkstra(0);

int sum = 0;

for (int i = 0; i < n; ++i)

{

sum += dist[fire[i]];

}

cout << sum << "\n";

}

return 0;

}