https://algospot.com/judge/problem/read/FIRETRUCKS
algospot.com :: FIRETRUCKS
소방차 문제 정보 문제 한겨울 날씨가 추워지면 각종 난방 기구 때문에 화재가 발생하기 쉽습니다. 어느 추운 겨울날 서울 시내 n개의 지역에 동시에 화재가 발생했습니다. 피해를 최소화하기 위해 가능한 한 빠르게 소방차를 파견해야 합니다. 서울 시내에는 m개의 소방서가 있습니다. 화재 장소에서 가장 가까운 소방서에서 소방차를 보낸다고 할 때, 각 화재 장소에 소방차가 도달하기까지 걸리는 시간의 합을 계산하는 프로그램을 작성하세요. 각 소방서에는 소방차가 충분
algospot.com
다익스트라의 다른 시각을 볼수 있는 문제로,
기본 사상인 : 한 점에서 시작하여, 여러점의 최단거리를 측정하는 문제의 확장 판인듯함.
소방서의 여러점을 동시에 넣고 전체 지점의 최단거리를 구하면 되는 문제
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Firetrucks {
static int V, E, n, m;
static ArrayList<Edge>[] edges;
static int[] Fire;
static int[] D;
static class Edge implements Comparable<Edge> {
int e, v;
Edge(int e, int v){
this.e = e;
this.v = v;
}
@Override
public int compareTo(Edge o) {
return this.v - o.v;
}
}
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("res/input_firetrucks.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int T = Integer.parseInt(br.readLine().trim());
for (int t = 1; t <= T ; t++) {
st = new StringTokenizer(br.readLine().trim(), " ");
V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
edges = new ArrayList[V+1];
Fire = new int[n];
D = new int[V+1];
Arrays.fill(D, Integer.MAX_VALUE);
int a, b ,c;
for (int i = 0; i < E ; i++) {
st = new StringTokenizer(br.readLine().trim(), " ");
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
if(edges[a]==null) edges[a] = new ArrayList<>();
edges[a].add(new Edge(b, c));
if(edges[b]==null) edges[b] = new ArrayList<>();
edges[b].add(new Edge(a, c));
}
// fire Position
st = new StringTokenizer(br.readLine().trim(), " ");
for (int i = 0; i < n ; i++) {
Fire[i] = Integer.parseInt(st.nextToken());
}
PriorityQueue<Edge> pq = new PriorityQueue<>();
// Fire Station
st = new StringTokenizer(br.readLine().trim(), " ");
for (int i = 0; i < m ; i++) {
a = Integer.parseInt(st.nextToken());
pq.add(new Edge(a, 0));
}
// Dijkstra
Edge ed;
while (!pq.isEmpty()){
ed = pq.poll();
if(D[ed.e]<ed.v) continue;
D[ed.e] = ed.v;
if(edges[ed.e]==null) continue;
for (Edge nd: edges[ed.e]) {
if(D[nd.e]>D[ed.e]+nd.v) {
pq.add(new Edge(nd.e, D[ed.e]+nd.v));
}
}
}
long result = 0;
for (int i = 0; i < n; i++) {
result += D[Fire[i]];
}
System.out.println(result);
}
}
}