旅行(dijkstra) (坑爹的输入 fxxk)"/>
HDU2066 一个人的旅行(dijkstra) (坑爹的输入 fxxk)
Problem
这个题真的是对Java快速读入一点都不友好,调试了一小时,反复看,测试数据都没有问题,最后是边界问题的输入有问题,这**杭电OJ也不给看测试数据。
用的是迪杰。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static int N = 1010, n, T, S, D;static int g[][], dist[];static int wannago[];static boolean st[];static int INF = 1 << 28;public static void init() {g = new int[N][N];dist = new int[N];wannago = new int[N];st = new boolean[N];Arrays.fill(dist, INF);dist[0] = 0;for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++)g[i][j] = INF;g[i][i] = 0;}}public static void main(String[] args) throws IOException {while (true) {String input = br.readLine();if (input == null) break;init();String s[] = input.split(" ");T = Integer.parseInt(s[0]);S = Integer.parseInt(s[1]);D = Integer.parseInt(s[2]);for (int i = 0; i < T; i++) {s = br.readLine().split(" ");int a = Integer.parseInt(s[0]);int b = Integer.parseInt(s[1]);int time = Integer.parseInt(s[2]);n = Math.max(Math.max(a, b), n);g[a][b] = g[b][a] = Math.min(g[a][b], time);}input = br.readLine();if (input != null) {s = input.split(" ");for (int i = 0; i < S; i++) {int a = Integer.parseInt(s[i]);g[0][a] = g[a][0] = 0;dist[a] = 0;}}int res = INF;input = br.readLine();if (input != null) {s = input.split(" ");for (int i = 0; i < D; i++) {wannago[i] = Integer.parseInt(s[i]);}}dijkstra();for (int i = 0; i < D; i++) {res = Math.min(res, dist[wannago[i]]);}System.out.println(res);System.gc();}}public static void dijkstra() {for (int i = 0; i <= n; i++) {int t = -1;for (int j = 0; j <= n; j++) {if (!st[j] && (t == -1 || dist[t] > dist[j]))t = j;}st[t] = true;for (int j = 0; j <= n; j++) {dist[j] = Math.min(dist[j], dist[t] + g[t][j]);}}}}
更多推荐
HDU2066 一个人的旅行(dijkstra) (坑爹的输入 fxxk)
发布评论