https://www.acmicpc.net/problem/9370
9370번: 미확인 도착지
문제 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는 지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익) 어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다.
www.acmicpc.net
단순 다익스트라 문제인줄 알았는데..
문제 조차 이해하기 어려웠다..
시작 점에서 도착 예상 정점을 출력하라는 문제인데..
결국 풀이해보면.
[시작정점에서 도착 예상 정점의 최단거리 = 시작정점에서 주어진 간선까지의 최단거리 + 주어진간선부터 도착 예상정점으로의 최단거리] 로 풀릴 듯하다.
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 BOJ9370 {
static int n, m, t, s, g, h;
static boolean[] TB;
static int[] XD, YD;
static ArrayList<Edge>[] edges;
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_boj9370.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine().trim());
StringTokenizer st;
for (int te = 0; te < T ; te++) {
st = new StringTokenizer(br.readLine().trim(), " ");
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
t = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine().trim(), " ");
s = Integer.parseInt(st.nextToken());
g = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
edges = new ArrayList[n+1];
TB = new boolean[n+1];
XD = new int[n+1];
YD = new int[n+1];
int a, b, c;
for (int i = 0; i < m ; 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));
}
int x;
for (int i = 0; i < t ; i++) {
x = Integer.parseInt(br.readLine().trim());
TB[x] = true;
}
dijkstra(s, XD);
int bridge = (XD[g]<XD[h])? h : g; // big
dijkstra(bridge, YD);
StringBuffer sb = new StringBuffer();
for (int i = 1; i <=n ; i++) {
if(!TB[i]) continue;;
if((XD[i]==Integer.MAX_VALUE)||(YD[i]==Integer.MAX_VALUE)) continue;
if(XD[i] == XD[bridge] + YD[i]) {
sb.append(i);
sb.append(" ");
}
}
System.out.println(sb.toString());
}
}
static void dijkstra(int s, int[] D) {
Arrays.fill(D, Integer.MAX_VALUE);;
PriorityQueue<Edge> pq = new PriorityQueue<>();
Edge ed = new Edge(s, 0);
pq.add(ed);
D[s] = 0;
while (!pq.isEmpty()){
ed = pq.poll();
if(edges[ed.e]==null) continue;
for (Edge nd: edges[ed.e]) {
if(D[nd.e] > D[ed.e]+nd.v) {
D[nd.e] = D[ed.e] + nd.v;
pq.add(new Edge(nd.e, ed.v + nd.v));
}
}
}
}
}