글 읽기 - 마지막테스트케이스하나만 틀린것 같은데 무엇이문제일까요

qkrqudwn12 7년 전 0

99%프로 까지는 맞는데 머가 틀린지 모르겠습니다.

//이문제는 시작점을 t1 t2 로 놓고 t1->1 t1->t2 t2->n까지 가는것
// t2->1 t1->t2 t1->n
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class 특정한최단경로 {
	static int array[][] = new int[1000][1000];
	static int d[] = new int[1000];
	static int N;
	static int E;
	static int t1;
	static int t2;
	static PriorityQueue<Point5> q = new PriorityQueue<Point5>();
	static final int INF = 987654321;

	public static void bfs(int start) {
		Arrays.fill(d, INF);
		d[start] = 0;
		q.add(new Point5(start, 0));
		while (!q.isEmpty()) {
			Point5 p = q.poll();
			int x = p.x;
			int cost = p.cost;
			for (int i = 1; i <= N; i++) {
				if (array[x][i] > 0) {
					if (d[i] >= d[x] + array[x][i]) {
						d[i] = d[x] + array[x][i];
						q.add(new Point5(i, d[i]));
					} 
				}
			}
		}

	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		N = scan.nextInt();
		E = scan.nextInt();
		for (int i = 0; i < E; i++) {
			int start = scan.nextInt();
			int end = scan.nextInt();
			int cost = scan.nextInt();
			if (array[start][end] < cost && array[start][end] != 0)
				continue;
			array[start][end] = cost;
			array[end][start] = cost;
		}
		t1 = scan.nextInt();
		t2 = scan.nextInt();

		bfs(t1);
		int t1_to_1 = d[1];
		int t1_to_t2 = d[t2];
		int t1_to_N = d[N];
		bfs(t2);
		int t2_to_1 = d[1];
		int t2_to_t1 = d[t1];
		int t2_to_N = d[N];
		long case1 = t1_to_1 + t1_to_t2 + t2_to_N;
		long case2 = t2_to_1 + t2_to_t1 + t1_to_N;
		long min = case1 > case2 ? case2 : case1;
		if (case1 >= INF && case2 >= INF) {
			System.out.println(-1);
		} else {
			System.out.println(min);
		}

	}
}

class Point5 implements Comparable<Point5> {
	int x;
	int cost;

	Point5(int x, int cost) {
		this.x = x;
		this.cost = cost;
	}

	@Override
	public int compareTo(Point5 o) {
		if (cost > o.cost)
			return 1;
		else if (cost < o.cost)
			return -1;
		else
			return 0;

	}
}

hun222y 7년 전 0

문제 번호를 적어주셔야 ... ㅠ

qkrqudwn12 7년 전 0

1504번입니다.

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

문제

문제

출처

ICPC

마지막테스트케이스하나만 틀린것 같은데 무엇이문제일까요

qkrqudwn12 7년 전 0

hun222y 7년 전 0

qkrqudwn12 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말