[그래프] FIRETRUCKS 소방차
2021. 2. 19. 18:14ㆍ알고리즘/알고리즘 문제 [easy]
1. 문제
이 문제는 여러 소방서에서 불난집까지 가는 최단 거리들을 찾는 것이다.
이것은 불난집을 여러번 다익스트라를 돌려서 가장짧은 소방서를 찾으면 해결되지만
이 문제의 의도는 아니다.
(소방서를 기준으로 돌리거나 플로이드의 모든 쌍 최단 경로 알고리즘(O(V^3))을 이용하여 풀 수 도 있지만 느리다)
2. 모든 소방서를 하나로
이 문제는 모든 소방서를 한 소방서에 합치면 다익스트라 한번에 해결 할 수 있다.
다음은
모든 입력이 주어지고나서 첫번째 소방서에다가 하나로 합친 그래프를 만들고 문제를 해결하는 코드이다.
책에서는 인덱스 0 인 임의의 정점을 만들어서 이를 가중치가 0 으로 소방서를 전부 이었다.
이렇게하면 모든 소방서에서 동시에 다익스트라를 수행하는것과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
#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";
}
}
|
cs |
'알고리즘 > 알고리즘 문제 [easy]' 카테고리의 다른 글
[그래프] BISHOPS 비숍 (0) | 2021.02.26 |
---|---|
[그래프] TIMETRIP 시간여행 (0) | 2021.02.20 |
[그래프] ROUTING 신호 라우팅 (0) | 2021.02.19 |
[그래프] DICTIONARY 고대어 사전 (0) | 2021.02.12 |
[트리] MORDOR 등산로 (0) | 2021.02.07 |