[SWEA 5684] 운동(JAVA)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRxnnah2sDFAUo

SW Expert Academy

 

처음에 dfs로 잘못 생각해서 스택오버플로우가 났다. 다익스트라로 다시 생각해서 풀었다.

테스트케이스에 공백값들이 들어 있어서 BufferedReader를 사용하면 런타임에러가 뜨길래, Scanner로 입력을 받았다.

if(nowDist>ans) continue; 구문을 추가해주니 시간은 반절이상 줄었고, 메모리도 줄었다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.StringTokenizer;

class Node{
	int node;
	int val;
	public Node(int node, int val) {
		super();
		this.node = node;
		this.val = val;
	}
	
}
public class Solution_d4_5684_운동 {
	final static int INF= 987654321;
	static int N,M;//건물, 도로
	static List[] map;//연결체크
	static int[] dist;
	static int ans;
	static PriorityQueue<int[]> pq;
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int T=sc.nextInt();
		for(int tc=1; tc<=T; tc++) {
			ans=Integer.MAX_VALUE;
			N=sc.nextInt();
			M=sc.nextInt();
			map=new ArrayList[N+1];
			dist=new int[N+1];
	        for(int i = 1; i <= N; i++)
	        	map[i] = new ArrayList<>();
			for(int i=0; i<M; i++) {
				int s=sc.nextInt();
				int e=sc.nextInt();
				int c=sc.nextInt();
				map[s].add(new Node(e,c));
			}
			for(int i=1; i<=N; i++) {
				solve(i);
			}
			
			System.out.println("#"+tc+" "+(ans==Integer.MAX_VALUE? -1:ans));
		}

	}
	private static void solve(int start) {
		for(int i=1; i<=N; i++) {
			dist[i]=INF;
		}
		pq=new PriorityQueue<int[]>(new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return Integer.compare(o1[1], o2[1]);
			}
		});
		pq.offer(new int[] {start,0});
		while(!pq.isEmpty()) {
			int[] a=pq.poll();
			int now = a[0];
			int nowDist = a[1];
			if(now==start) {
				if(ans>dist[start])ans=dist[start];
			}
			if(nowDist>ans) continue;
			for(int i=0; i<map[now].size(); i++) {
				Node node = (Node) map[now].get(i);
				int next=node.node;
				int val=node.val;
				if(nowDist+val<dist[next]) {
					dist[next]=nowDist+val;
					pq.offer(new int[] {next,nowDist+val});
				}
				
			}
		}
		
		
	}

}