글 읽기 - 파티문제-다익스트라 알고리즘에서 무한루프?

bing9 6년 전 0

문제의 주요 쟁점? 은 알고 있습니다.

간선의 방향을 반대로 바꿔서 계산하면 각자의 마을 위치에서 파티마을로 가는 것도 효율적으로 구할 수 있다는 것을 알고 있습니다..

그런데 문제는 제 코드가 무한루프를 돕니다..

그래서 좀 디버깅 해보니까..

테스트 입력 예제가

이렇게 되는데.. 여기서 보면

2번이 파티마을이고 2번으로 시작해서 다른 마을로의 최단경로를 구하다보면

2->1->2번 이렇게 갈 수 있듯이 계속 2번이 큐에 들어오면서 무한루프를 돌게 됩니다..

어떻게 해결방법이 없을까요?

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Al1238 {
	static int Vn;
	static int En;
	static int P;
	static ArrayList<ArrayList<Line>> comeAd;
	static ArrayList<ArrayList<Line>> goAd;
	static int[] comeDist;
	static int[] goDist;
	static int[] totalDist;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Vn = sc.nextInt();
		En = sc.nextInt();
		P = sc.nextInt();
		comeAd = new ArrayList<>();
		goAd = new ArrayList<>();
		comeDist = new int[Vn+1];
		goDist = new int[Vn+1];
		totalDist = new int[Vn+1];
		for(int i=0; i<comeDist.length; i++) {
			comeDist[i] = goDist[i] = Integer.MAX_VALUE;
			comeAd.add(i, new ArrayList<Line>());
			goAd.add(i, new ArrayList<Line>());
		}
		for(int i=0; i<En; i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			int w = sc.nextInt();
			comeAd.get(u).add(new Line(v,w));
			goAd.get(v).add(new Line(u,w));
		}
		dijkstra(P, comeDist, comeAd);
		dijkstra(P, goDist, goAd);
		for(int data : comeDist) {
			System.out.print(data+" ");
		}System.out.println();
		for(int data : goDist) {
			System.out.print(data+" ");
		}System.out.println();
		for(int i=0; i<comeDist.length; i++) {
			totalDist[i] = comeDist[i] + goDist[i];
		}
		Arrays.sort(totalDist);
		System.out.print(totalDist[totalDist.length-1]);
	}
	public static void dijkstra(int start, int[] dist, ArrayList<ArrayList<Line>> ad) {
		PriorityQueue<Line> q = new PriorityQueue<>();
		dist[start] = 0;
		q.offer(new Line(start, dist[start]));
		while(!q.isEmpty()) {
			int nowVertex = q.peek().getV();
			int cost = q.peek().getW();
			q.poll();
			if(cost > dist[nowVertex]) continue;
			for(Line line : ad.get(nowVertex)) {
				int nextVertex = line.getV();
				int oldDist = dist[nextVertex];
				int newDist = dist[nowVertex] + line.getW(); 
				dist[nextVertex] = oldDist > newDist ? newDist : oldDist;
				q.offer(new Line(nextVertex, dist[nextVertex]));
			}
		}
	}
	static class Line implements Comparable<Line> {
		private int v;
		private int w;
		public Line(int v, int w) {
			this.v = v;
			this.w = w;
		}
		public int getV() {
			return v;
		}
		public int getW() {
			return w;
		}
		@Override
		public int compareTo(Line o) {
			return this.w-o.w;
		}		
	}
}

bing9 6년 전 0

스스로 해결;

daniel060811 3년 전 0

잘은 모르지만 갔던 곳은 체크만들어서 하면 되지 않을까요?

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

문제

문제

출처

ICPC

파티문제-다익스트라 알고리즘에서 무한루프?

bing9 6년 전 0

bing9 6년 전 0

daniel060811 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말