暢通工程續(xù)
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 59078 Accepted Submission(s): 22176
Problem Description
某省自從實行了很多年的暢通工程計劃后，終于修建了很多路憔鬼。不過路多了也不好龟劲，每次要從一個城鎮(zhèn)到另一個城鎮(zhèn)時，都有許多種道路方案可以選擇轴或，而某些方案要比另一些方案行走的距離要短很多昌跌。這讓行人很困擾。
?
現(xiàn)在照雁，已知起點和終點蚕愤，請你計算出要從起點到終點，最短需要行走多少距離饺蚊。
?
Input
?
本題目包含多組數(shù)據(jù)萍诱，請?zhí)幚淼轿募Y(jié)束。
?
每組數(shù)據(jù)第一行包含兩個正整數(shù)N和M(0<N<200,0<M<1000)污呼，分別代表現(xiàn)有城鎮(zhèn)的數(shù)目和已修建的道路的數(shù)目裕坊。城鎮(zhèn)分別以0～N-1編號。
?
接下來是M行道路信息曙求。每一行有三個整數(shù)A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城鎮(zhèn)A和城鎮(zhèn)B之間有一條長度為X的雙向道路碍庵。
?
再接下一行有兩個整數(shù)S,T(0<=S,T<N)，分別代表起點和終點悟狱。
?
Output
?
對于每組數(shù)據(jù)静浴，請在一行里輸出最短需要行走的距離。如果不存在從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
這道題可以使用很多種方法來解dijkltra苹享、floyd、最小生成樹等，我這里選擇的是dijkltra算法https://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html
?
當中需要注意的是兩個城鎮(zhèn)之間可能會有多條可通過的路徑得问，因此在二維數(shù)組初始化時就應(yīng)該選擇最短的一條
package acm1874;
/**
* date:2017.12.17
* author:孟小德
* function:杭電acm1874
* 暢通工程續(xù) 單源最短路徑 迪杰斯特拉算法
*/
import java.util.*;
public class Main
{
public static int MAXINT = 200000000; //最大長度表示無法聯(lián)通
public static int NUM_OF_NODE; //城鎮(zhèn)的數(shù)量
public static int NUM_OF_EDGE; //道路的數(shù)量
public static int[] PATH; //記錄到每個城鎮(zhèn)的最短路徑
public static int[][] MAP; //一個二維數(shù)組記錄城鎮(zhèn)的道路情況
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();
}
}
