HDU1874（最短路径）

[java]
package D0801;

//最短路径问题（dijkstra算法）
import java.util.*;

public class HDU1874 {

    static int n;// n个城市（n个点）
    static int[][] map;// 邻接矩阵
    static int[] pre;// 记录前驱点、原点、终点。若pre[i]=k,表示从s到i的最短路径中i的前一个点是k
    static int[] dist;// s到终点的最短路径
    static int s, e;// 原点、终点

    public static void dijkstra() {
        boolean[] p = new boolean[n];// 记录改点是否属于集合a或b
        // 初始化
        for (int i = 0; i < n; 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<n-1;i++){
            int min = Integer.MAX_VALUE;//s到某个点的最短路径
            int k = -1;
            //在集合b中寻找从s到其路径最短的的点k
            for(int j = 0;j<n;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<n;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);
        int m;
        while (sc.hasNext()) {
            n = sc.nextInt();
            m = sc.nextInt();
            map = new int[n][n];
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    map[i][j] = Integer.MAX_VALUE;
            pre = new int[n];
            dist = new int[n];
            while (m-- > 0) {
                int u = sc.nextInt();
                int v = sc.nextInt();
                int w = sc.nextInt();
                if (map[u][v] > w || map[v][u] > w) {//注意是双向的
                    map[u][v] = w;
                    map[v][u] = w;
                }
            }
            s = sc.nextInt();
            e = sc.nextInt();
            dijkstra();
            if (dist[e] == Integer.MAX_VALUE)
                System.out.println(-1);
            else
                System.out.println(dist[e]);
        }
    }

}
作者：lhfight

补充：软件开发 , Java ,