1504번 특정한 최단 경로 G4

 

 

 문제는 간단하다.

 

1번 정점부터 N번 정점까지 최단 거리를 구하는데,

 

U정점과 V정점을 반드시 거쳐야 하는 것이다.

 

일단 처음 문제를 보면 해당 정점까지의 최단 거리를 구하는 다익스트라를 떠올릴 수 있겠다.

 

그리고 정적으로 2정점을 지난다는 것이 조건이니 두 개의 정점을 지난다는 걸 구현하면 된다.

 

그렇다면 일단 1을 시작 정점으로 해서 모든 정점으로 향하는 최단 거리를 구하고,

 

또 U 정점을 시작정점으로 구하고, V 정점을 시작정점으로 구한 뒤,

 

1부터 U까지, U에서 V까지, V에서 N까지 최단 거리와

 

1부터 V까지, V에서 U까지, U에서 N까지 최단 거리를 비교한 후 최단 거리를 출력하면 되지 않을까? 생각했다.

 

 

여기서 중요한 것은 만약 1에서 부터 두 정점을 지나 N까지 가는 경우가 없다면 -1을 출력하는 것이다. 

 

간선이 0이라는 조건도 있으니 0일 경우 바로 -1을 출력하는 것도 시간을 줄이기 좋을 것이다.

 

이런 생각을 가지고 문제를 풀었다. 

 

이후의 문제는 다익스트라를 3번 돌리면 되는 것이니 전체 코드를 보면 된다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
	static int n;
	static int e;
	static LinkedList<Node>[]list;
	static int [] dist;
	static int [] dist1;
	static int [] dist2;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n =Integer.parseInt(st.nextToken());
		e = Integer.parseInt(st.nextToken());
		
		list=new LinkedList[n+1];
		for(int i=0;i<=n;i++) {
			list[i]=new LinkedList<>();
		}
		dist = new int [n+1];
		dist1 = new int [n+1];
		dist2 = new int [n+1];
		Arrays.fill(dist, Integer.MAX_VALUE);
		Arrays.fill(dist1, Integer.MAX_VALUE);
		Arrays.fill(dist2, Integer.MAX_VALUE);
		for(int i=0;i<e;i++) {
			st = new StringTokenizer(br.readLine());
			int a=Integer.parseInt(st.nextToken());
			int b=Integer.parseInt(st.nextToken());
			int d=Integer.parseInt(st.nextToken());
			list[a].add(new Node(b,d));
			list[b].add(new Node(a,d));
		}
		st= new StringTokenizer(br.readLine());
		int u=Integer.parseInt(st.nextToken());
		int v=Integer.parseInt(st.nextToken());
		if(e>0) {
		dijkstra(1,dist);
		dijkstra(u,dist1);
		dijkstra(v,dist2);
		int sum=0;
		if(dist[u]!=Integer.MAX_VALUE&&dist2[n]!=Integer.MAX_VALUE)
			sum+=dist[u]+dist1[v]+dist2[n];
		if(dist[v]!=Integer.MAX_VALUE&&dist1[n]!=Integer.MAX_VALUE)
			sum=Math.min(sum, dist[v]+dist2[u]+dist1[n]);
		if(sum!=0)
			bw.write(String.valueOf(sum));
		else
			bw.write("-1");
		}
		else {
			bw.write("-1");
		}
		bw.close();
		br.close();
		
	}
	private static void dijkstra(int st,int []dist) {
		// TODO Auto-generated method stub
		boolean[] v= new boolean[n+1];
		dist[st]=0;
		for(int i=0;i<n-1;i++) {
			int min=Integer.MAX_VALUE;
			int idx=-1;
			for(int j=1;j<=n;j++) {
				if(!v[j]&&min>dist[j]) {
					min=dist[j];
					idx=j;
				}
			}
			
			if(idx==-1)break;
			v[idx]=true;
			for(int j=0;j<list[idx].size();j++) {
				Node cur= list[idx].get(j);
				if(!v[cur.v]&&dist[cur.v]>dist[idx]+cur.d) {
					dist[cur.v]=dist[idx]+cur.d;
				}
			}
		}
		
	}
}
class Node{
	int v;
	int d;
	Node(int v,int d){
		this.v=v;
		this.d=d;
	}
}