소방차 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;
}
