杭电acm1874-畅通工程续

 

一、Problem Description

某省自从实行了很多年的畅通工程计划后，终于修建了很多路。不过路多了也不好，每次要从一个城镇到另一个城镇时，都有许多种道路方案可以选择，而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。
 
现在，已知起点和终点，请你计算出要从起点到终点，最短需要行走多少距离。
 
Input
 
本题目包含多组数据，请处理到文件结束。
 
每组数据第一行包含两个正整数N和M(0<N<200,0<M<1000)，分别代表现有城镇的数目和已修建的道路的数目。城镇分别以0～N-1编号。
 
接下来是M行道路信息。每一行有三个整数A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城镇A和城镇B之间有一条长度为X的双向道路。
 
再接下一行有两个整数S,T(0<=S,T<N)，分别代表起点和终点。
 
Output
 
对于每组数据，请在一行里输出最短需要行走的距离。如果不存在从S到T的路线，就输出-1.
 
Sample Input
 
3 3 0 1 1 0 2 3 1 2 1 0 2 3 1 0 1 1 1 2
 
Sample Output
 
2
 
-1

二、Solution

这道题可以使用很多种方法来解dijkltra、floyd、最小生成树等，我这里选择的是dijkltra算法https://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html
 
当中需要注意的是两个城镇之间可能会有多条可通过的路径，因此在二维数组初始化时就应该选择最短的一条

三、Code

package acm1874;

/**

* date:2017.12.17

* author:孟小德

* function:杭电acm1874

*      畅通工程续  单源最短路径  迪杰斯特拉算法

*/







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=0;i<NUM_OF_NODE;i++)

        {

            PATH[i] = MAP[v0][i];

            S[i] = false;

        }

        PATH[v0] = 0;

        S[v0] = true;

        for (int i=1;i<NUM_OF_NODE;i++)

        {

            int minpath = MAXINT;

            int u = v0;



            for (int j=0;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=0;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);



        while (input.hasNextInt())

        {

            NUM_OF_NODE = input.nextInt();

            NUM_OF_EDGE = input.nextInt();



            MAP = new int[NUM_OF_NODE][NUM_OF_NODE];

            PATH = new int[NUM_OF_NODE];

            S = new boolean[NUM_OF_NODE];

            for (int i=0;i<NUM_OF_NODE;i++)

            {

                // PATH[i] = MAXINT;

                // S[i] = false;

                for (int j=0;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;

                }

            }

            int v0 = input.nextInt();

            int v = input.nextInt();

            dijkstra(v0);

            if (PATH[v] == MAXINT)

            {

                System.out.println(-1);

            }

            else

            {



                System.out.println(PATH[v]);

            }



        }



        input.close();

    }

}

最后更新： 2018年12月27日 18:58

原始链接： https://cwhong.top/2018/12/25/程序日记本/杭电acm1874-畅通工程续/

cwhong

赏

× Thank you~