글 읽기 - 시간초과 해결을 못하겠습니다ㅜㅜ 도움 주시면 정말 감사하겠습니다

sunsmile11 4년 전 0

채점되다가 시간초과가 자꾸 뜨는데 어디를 고쳐야하는지 도저히 해결방법을 못찾겠어서 올립니다

visited를 이용하는것 같은데 추가하면 자꾸 틀렸습니다 가 뜨더군요

어떻게 해결하면 좋을까요,,

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

	static class Pair implements Comparable<Pair> {
		int v;
		int w;

		public Pair(int v, int w) {
			this.v = v;
			this.w = w;
		}

		@Override
		public int compareTo(Pair p) {
			// TODO Auto-generated method stub
			return p.w <= this.w ? 1 : -1;
		}
	}

	static int MAX = 999999;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		// 다익스트라 알고리즘

		Scanner sc = new Scanner(System.in);

		int V = sc.nextInt();
		int E = sc.nextInt();
		int start = sc.nextInt();

		int[] d = new int[V + 1];
		boolean[] visited = new boolean[V + 1];
		LinkedList<Pair> adj[] = new LinkedList[V + 1];

		for (int i = 1; i <= V; i++) {
			adj[i] = new LinkedList();
		}

		for (int i = 0; i < E; i++) {
			// u에서 v로 가는 가중치 w
			int u = sc.nextInt();
			int v = sc.nextInt();
			int w = sc.nextInt();

			adj[u].add(new Pair(v, w));
		}

		for (int i = 1; i <= V; i++) {
			d[i] = MAX;
			visited[i]=false;
			// for(int j=0;j<adj[i].size();j++) {
			// System.out.print(adj[i].get(j).v);
			//
			// }
			// System.out.println();
		}

		PriorityQueue<Pair> q = new PriorityQueue<Pair>();

		d[start] = 0;
		q.add(new Pair(start, 0));

		while (!q.isEmpty()) {
			Pair p = q.poll();
			int curV = p.v;
			int curW = p.w;

			visited[curV]=true;
			
			if(d[curV]<curW) continue;

			for (int i = 0; i < adj[curV].size(); i++) {

				int adjV = adj[curV].get(i).v;
				int adjW = adj[curV].get(i).w;
				
				
				if(d[curV]+adjW<d[adjV]) {

					d[adjV] = Math.min(d[adjV], d[curV] + adjW);
					q.add(new Pair(adjV, adjW));
				}

				

			}

		}

		for (int i = 1; i <= V; i++) {
			if (d[i] == MAX)
				System.out.println("INF");
			else
				System.out.println(d[i]);
		}

	}

}

djm03178 4년 전 0

https://www.acmicpc.net/board/...

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 해결을 못하겠습니다ㅜㅜ 도움 주시면 정말 감사하겠습니다

sunsmile11 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말