findthepath.java

第四届百度杯编程大赛final解题报告+标程

import java.io.*;
import java.util.*;

public class FindThePath {

	public static class que_type implements Comparable {
		public int k, op;

		public que_type(int kk, int oo) {
			k = kk;
			op = oo;
		}

		public int compareTo(Object obj) {
			if (obj instanceof que_type) {
				que_type x = (que_type) obj;
				if (this.k < x.k) {
					return -1;
				} else
					return 1;
			}
			return 0;
		}
	}

	public static final int maxSize = 200 + 10;

	static int n, m;

	static int f[][][] = new int[maxSize][maxSize][maxSize];

	static int g[] = new int[maxSize];

	static que_type[] que;

	static Scanner in = new Scanner(System.in);
	
	public static void init() {
		for (int i = 0; i <= n; i ++) {
			for (int j = 1; j <= n; j ++) {
				for (int k = 1; k <= n; k ++) {
					f[i][j][k] = -1;
				}
			}
		}
		que = new que_type[n + 1];
		que[0] = new que_type(-1, 0);
		for (int i = 1; i <= n; i++) {
			que[i] = new que_type(in.nextInt(), i);
		}
		Arrays.sort(que);
		for (int i = 1; i <= n; i++)
			g[que[i].op] = i;
		for (int i = 0; i < m; i++) {
			int x, y, z;
			x = in.nextInt();
			y = in.nextInt();
			z = in.nextInt();
			x++;
			y++;
			f[0][g[x]][g[y]] = f[0][g[y]][g[x]] = z;
		}
	}

	public static int getmin(int a, int b) {
		if (a == -1 || a > b)
			return b;
		else
			return a;
	}

	public static void solve() throws Exception {
		for (int k = 1; k <= n; k++)
			for (int i = 1; i <= n; i++)
				for (int j = 0; j <= n; j++) {
					if (f[k - 1][i][k] != -1
							&& f[k - 1][k][j] != -1
							&& (f[k - 1][i][k] + f[k - 1][k][j] < f[k][i][j] || f[k][i][j] == -1))
						f[k][i][j] = f[k - 1][i][k] + f[k - 1][k][j];
					if (f[k - 1][i][j] != -1)
						f[k][i][j] = getmin(f[k][i][j], f[k - 1][i][j]);
				}

		int Q;
		Q = in.nextInt();
		while (Q > 0) {
			Q--;
			int x, y, k;
			x = in.nextInt();
			y = in.nextInt();
			k = in.nextInt();
			x = g[++x];
			y = g[++y];
			int l = 1, r = n, t = 0;
			while (l <= r) {
				int mid = (l + r) / 2;
				if (que[mid].k <= k) {
					t = Math.max(t, mid);
					l = mid + 1;
				} else
					r = mid - 1;
			}
			int p = f[t][x][y];
			char[] buf = new char[20];
			int len = 0;
			while (p != 0) {
				buf[len ++] = (char) (p % 10);
				p /= 10;
			}
			System.out.println((Integer.valueOf(f[t][x][y]).toString()).toCharArray());
		}
	}

	public static void main(String arg[]) throws Exception {
		int test_num = in.nextInt();
		while (test_num -- > 0) {
			n = in.nextInt();
			m = in.nextInt();
			if (n == 0 && m == 0)
				break;
			init();
			solve();
			System.out.println();
		}
	}
}