글 읽기 - 질문드립니다 !

aldrlsb11 5년 전 0

다익스트라 개념을 떠올리면서 코드를 만들어봤습니다

문제가 있는지 자꾸 틀리게 나오는데 도와주시면 감사하겠습니다 !

node간 edge가 없는 경우는 g[][] == -1로 처리했습니다

public class Main {
	public static int n, e, st, g[][], d[], end;
	public static boolean v[];

	public static void dijk(int st) {
		PriorityQueue<Element> pq = new PriorityQueue<>();
		d[st] = 0;
		pq.add(new Element(st, 0));
		while(!pq.isEmpty()) {
			Element now = pq.poll();
			int here = now.desti;
			v[here] = true;
			for (int i = 1; i <= n; i++) {
				if (v[i]) {
					continue;
				}
				if (g[here][i] == -1) {
					continue;
				}
				if (d[i] <= d[here] + g[here][i]) {
					continue;
				}
				d[i] = d[here] + g[here][i];
				pq.add(new Element(i, d[i]));
			}
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		g = new int[n + 1][n + 1];
		d = new int[n + 1];
		v = new boolean[n + 1];
		Arrays.fill(d, Integer.MAX_VALUE);
		for (int i = 0; i < n + 1; i++) {
			Arrays.fill(g[i], -1);
		}
		e = sc.nextInt();
		for (int i = 0; i < e; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();
			g[a][b] = c;
			g[b][a] = c;
		}
		st = sc.nextInt();
		end = sc.nextInt();
		dijk(st);
		System.out.println(d[end]);
	}
}

class Element implements Comparable<Element> {
	int desti;
	int weight;

	public Element(int hear, int weight) {
		this.desti = hear;
		this.weight = weight;
	}

	@Override
	public int compareTo(Element o) {
		return this.weight - o.weight;
	}
}

djm03178 5년 전 0

a에서 b로 가는 것은 a에서 b로만 갈 수 있는 것이지 b에서 a로 올 수 있는 건 아닙니다.

그리고 a에서 b로 가는 버스가 여럿 있을 수 있고 그 중에 최소 비용인 것만 남겨야 합니다.

aldrlsb11 5년 전 0

감사합니다 조언 반영해서 풀었습니다 !

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

문제

문제

출처

ICPC

질문드립니다 !

aldrlsb11 5년 전 0

djm03178 5년 전 0

aldrlsb11 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말