最短路

Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 73406 Accepted Submission(s): 32011

Problem Description

在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？
 
Input
输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。
输入保证至少存在1条商店到赛场的路线。
 
Output
对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间
 
Sample Input
2 1 1 2 3 3 3 1 2 5 2 3 5 3 1 2 0 0
 
Sample Output
3
2

Solution

一个简单的最短路问题，用dijkstra,floyd等都可以解，我一开始用的是并查集但是出错了

Code

package acm2544;
 
/**
 * date:2017.12.18
 * author:孟小德
 * function:杭电acm2544 最短路
 *  最小生成树，并查集
 */
 
import java.util.*;
 
public class Main
{
 
    public static int MAXINT = 200000000;   //最大长度表示无法联通
    public static int NUM_OF_NODE;      //城镇的数量
    public static int NUM_OF_EDGE;      //道路的数量
    public static int[] PATH;           //记录到每个城镇的最短路径
    public static int[][] MAP;          //一个二维数组记录城镇的道路情况
    public static boolean[] S;
 
    public static void dijkstra(int v0)
    {
        for (int i=1;i<=NUM_OF_NODE;i++)
        {
            PATH[i] = MAP[v0][i];
            S[i] = false;
        }
        PATH[v0] = 0;
        S[v0] = true;
        for (int i=2;i<=NUM_OF_NODE;i++)
        {
            int minpath = MAXINT;
            int u = v0;
 
            for (int j=1;j<=NUM_OF_NODE;j++)
            {
                if (S[j] == false && PATH[j] < minpath)
                {
                    u = j;
                    minpath = PATH[j];
                }
            }
            S[u] = true;    //找到的当前点
            // System.out.println(u);
 
            for (int j=1;j<=NUM_OF_NODE;j++)
            {
                if (S[j] == false && MAP[u][j] < MAXINT)
                {//通过当前点u找到其他点到v0的最短路径
                    // System.out.println("#");
                    // System.out.println(u + " " + j);
                    // System.out.println(PATH[j]);
                    // System.out.println(PATH[u] + " " + MAP[u][j]);
                    if (PATH[u] + MAP[u][j] < PATH[j])
                    {
                        PATH[j] = PATH[u] + MAP[u][j]; //更新最短路径
 
                    }
                }
            }
        }
    }
 
    public static void main(String[] args)
    {
        Scanner input = new Scanner(System.in);
 
        NUM_OF_NODE = input.nextInt();
        NUM_OF_EDGE = input.nextInt();
        while (NUM_OF_NODE != 0 || NUM_OF_NODE != 0)
        {
 
            MAP = new int[NUM_OF_NODE + 1][NUM_OF_NODE + 1];
            PATH = new int[NUM_OF_NODE + 1];
            S = new boolean[NUM_OF_NODE + 1];
            for (int i=1;i<=NUM_OF_NODE;i++)
            {
                // PATH[i] = MAXINT;
                // S[i] = false;
                for (int j=1;j<=NUM_OF_NODE;j++)
                {
                    MAP[i][j] = MAXINT;
                }
            }
 
            for (int i=0;i<NUM_OF_EDGE;i++)
            {
                int A = input.nextInt();
                int B = input.nextInt();
                int X = input.nextInt();
 
                if (MAP[A][B] > X)
                {
                    MAP[A][B] = X;
                    MAP[B][A] = X;
                }
            }
 
            dijkstra(1);
 
            System.out.println(PATH[NUM_OF_NODE]);
 
            NUM_OF_NODE = input.nextInt();
            NUM_OF_EDGE = input.nextInt();
 
        }
 
        input.close();
    }
}