最短路

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

Problem Description

在每年的校賽里，所有進(jìn)入決賽的同學(xué)都會(huì)獲得一件很漂亮的t-shirt。但是每當(dāng)我們的工作人員把上百件的衣服從商店運(yùn)回到賽場(chǎng)的時(shí)候，卻是非常累的！所以現(xiàn)在他們想要尋找最短的從商店到賽場(chǎng)的路線，你可以幫助他們嗎？
?
Input
輸入包括多組數(shù)據(jù)。每組數(shù)據(jù)第一行是兩個(gè)整數(shù)N、M（N<=100，M<=10000），N表示成都的大街上有幾個(gè)路口，標(biāo)號(hào)為1的路口是商店所在地，標(biāo)號(hào)為N的路口是賽場(chǎng)所在地，M則表示在成都有幾條路。N=M=0表示輸入結(jié)束。接下來(lái)M行，每行包括3個(gè)整數(shù)A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A與路口B之間有一條路，我們的工作人員需要C分鐘的時(shí)間走過(guò)這條路。
輸入保證至少存在1條商店到賽場(chǎng)的路線。
?
Output
對(duì)于每組輸入，輸出一行，表示工作人員從商店走到賽場(chǎng)的最短時(shí)間
?
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

一個(gè)簡(jiǎn)單的最短路問(wèn)題，用dijkstra,floyd等都可以解，我一開始用的是并查集但是出錯(cuò)了

Code

package acm2544;
 
/**
 * date:2017.12.18
 * author:孟小德
 * function:杭電acm2544 最短路
 *  最小生成樹，并查集
 */
 
import java.util.*;
 
public class Main
{
 
    public static int MAXINT = 200000000;   //最大長(zhǎng)度表示無(wú)法聯(lián)通
    public static int NUM_OF_NODE;      //城鎮(zhèn)的數(shù)量
    public static int NUM_OF_EDGE;      //道路的數(shù)量
    public static int[] PATH;           //記錄到每個(gè)城鎮(zhèn)的最短路徑
    public static int[][] MAP;          //一個(gè)二維數(shù)組記錄城鎮(zhèn)的道路情況
    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;    //找到的當(dāng)前點(diǎn)
            // System.out.println(u);
 
            for (int j=1;j<=NUM_OF_NODE;j++)
            {
                if (S[j] == false && MAP[u][j] < MAXINT)
                {//通過(guò)當(dāng)前點(diǎn)u找到其他點(diǎn)到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();
    }
}