hdu3790最短路径问题 （Dijkstra算法）

最短路径问题
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 32544    Accepted Submission(s): 9565



Problem Description

给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。




Input

输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点。n和m为0时输入结束。
(1<n<=1000, 0<m<100000, s != t)




Output

输出 一行有两个数， 最短距离及其花费。




Sample Input

3 2
1 2 5 6
2 3 4 5
1 3
0 0





Sample Output

9 11

解题步骤：
注意：map[a][b],cost[a][b]分别表示ab的路径长度与花费

1. 初始化操作：初始化map与cost，注意如果a=b时候为顶点到自身，因此初始化为0，其他为INF方便后面求解
2. 输入操作：在输入的时候不仅存储map与cost也要选出a、b之间路径最短与花费最低的值，因为可以输入数据有a、b有多条路径直接相连接。
3. 进入Dijkstra方法内变量与数组的定义：定义要用到的访问数组vis[]、存两点直接最短路径的数组d[]、存两点之间最小花费的数组c[]、要用到的常量Min做比较操作。
4. 初始化最短路径数组d[]、存两点之间最小花费的数组c[]，遍历map与cost求start起始点到end终止点的值，初始化完成后标记第一个start顶点已经访问过。
5. 第一次遍历n个顶点，如果end终点

package com.test;

import java.util.Scanner;

public class Main {
    static int maxn = 1007;
    static int INF = 65535;
    static int start, e;
    static int n, m;
    static int[][] map = new int[maxn][maxn];
    static int[][] cost = new int[maxn][maxn];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            n = sc.nextInt();
            m = sc.nextInt();
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    map[i][j] = i == j ? 0 : INF;
                    cost[i][j] = i == j ? 0 : INF;
                }
            }
            int a, b, c, d;
            for (int i = 1; i <= m; i++) {
                a = sc.nextInt();
                b = sc.nextInt();
                c = sc.nextInt();
                d = sc.nextInt();
                if (map[a][b] > c) {
                    map[a][b] = map[b][a] = c;
                    cost[a][b] = cost[b][a] = d;
                } else if (map[a][b] == c) {
                    if (cost[a][b] > d)
                        cost[a][b] = cost[b][a] = d;
                }
            }
            start=sc.nextInt();
            e=sc.nextInt();
            Dijkstra();
        }
    }

    private static void Dijkstra() {
        int v = 0,Min;
        int[] vis = new int[maxn];
        int[] d = new int[maxn];
        int[] c = new int[maxn];
        for(int i = 1;i <= n;i++) {
            d[i] = map[start][i];
            c[i] = cost[start][i];
        }
        vis[start]=1;//标记访问过
        for(int i=1;i<=n;i++){
// if(vis[e]==1){//终点已经遍历了直接跳出循环
// break;
// }
            Min=INF;
            for(int j=1;j<=n;j++){
                //如果该顶点没有访问过并且
                if(vis[j]==0&&d[j]<Min){
                    v=j;
                    Min=d[j];
                }
            }
            vis[v]=1;//标记访问
            for(int j=1;j<=n;j++){
                //map[v][j]表示v到j的路径长度
                if(vis[j]==0&&map[v][j]<INF){
                    if(d[j]>d[v]+map[v][j]){
                        d[j]=d[v]+map[v][j];
                        c[j]=c[v]+cost[v][j];
                    }else if(d[j]==d[v]+map[v][j]){
                        if(c[j]>c[v]+cost[v][j]){
                            c[j]=c[v]+cost[v][j];
                        }
                    }
                }
            }
        }
        System.out.println(d[e]+" "+c[e]);
    }
}