HDU2066（多原点终点的最短路径）

[java]
package D0801;

import java.util.*;

public class HDU2066 {
    static int t, s, d;
    static int[][] map;// 邻接矩阵
    static int[] pre;// 记录前驱点、原点、终点。若pre[i]=k,表示从s到i的最短路径中i的前一个点是k
    static int[] dist;// s到终点的最短路径
    static int[] start,end;// 原点、终点
    public static void dijkstra(int s) {
        boolean[] p = new boolean[1001];// 记录改点是否属于集合a或b
        // 初始化
        for (int i = 0; i < 1001; i++) {
            p[i] = false;
            if (i != s) {
                dist[i] = map[s][i];
                pre[i] = s;
            }
        }
        dist[s] = 0;// 原点到自己的距离为0；
        p[s] = true;
        // 循环n-1次，求s点到其它点的最短路径
        for (int i = 0; i < 1001; i++) {
            int min = Integer.MAX_VALUE;// s到某个点的最短路径
            int k = -1;
            // 在集合b中寻找从s到其路径最短的的点k
            for (int j = 0; j < 1001; j++) {
                if (!p[j] && dist[j] < min) {
                    min = dist[j];
                    k = j;
                }
            }
            if (k == -1)
                return;// 已经找完了，没有点可以扩展
            p[k] = true;// 将点k加入集合a
            // 更新s到集合b中的点的路劲长度
            for (int j = 0; j < 1001; j++) {
                if (!p[j] && map[k][j] != Integer.MAX_VALUE && dist[j] > dist[k] + map[k][j])
                    dist[j] = dist[k] + map[k][j];
                pre[j] = k;
            }
        }

    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            t = sc.nextInt();
            s = sc.nextInt();
            d = sc.nextInt();
            start = new int[s];
            end = new int[d];
            map = new int[1001][1001];
            for(int i = 0;i<1001;i++)
                for(int j = 0;j<1001;j++)
                    map[i][j] = Integer.MAX_VALUE;
            pre = new int[1001];
            dist = new int[1001];
            while (t-- > 0) {
                int u = sc.nextInt();
                int v = sc.nextInt();
                int w = sc.nextInt();
                if (map[u][v] > w) {//双向
                    map[u][v] = w;
                    map[v][u] = w;
                }

            }
            //原点
            for(int i = 0;i<s;i++)
                start[i]= sc.nextInt();
            //终点
            for(int i = 0;i<d;i++)
                end[i]=sc.nextInt();
            int min = Integer.MAX_VALUE;//最短路径
            //循环求从原点到某个终点的最短路径得最小的
            for(int i = 0;i<s;i++){
                dijkstra(start[i]);
                for(int j = 0;j<d;j++){
                    if(dist[end[j]]<min)
       &nb

补充：软件开发 , Java ,