?

某省自從實行了很多年的暢通工程計劃后，終于修建了很多路。不過路多了也不好，每次要從一個城鎮到另一個城鎮時，都有許多種道路方案可以選擇，而某些方案要比另一些方案行走的距離要短很多。這讓行人很困擾。

現在，已知起點和終點，請你計算出要從起點到終點，最短需要行走多少距離。

?

?

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

?

//Dijst...,算法和Prim差不多

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string.h>
using namespace std;
int main()
{
??? int n,s,t,m,i,j,min,cost;
??? int p[203][203],b[203];
??? while(scanf("%d%d",&n,&m)!=EOF)
??? {? memset(b,0,sizeof(b));
??????? for(i=0;i<n;i++)
????????? for(j=0;j<n;j++)
???????????? p[i][j]=0x7ffffff;
??????? for(min=0;min<m;min++)
??????? {
??????????? scanf("%d%d%d",&i,&j,&cost);
??????????? p[i][j]=p[j][i]=cost<p[i][j]?cost:p[i][j];
??????? }
??????? scanf("%d%d",&s,&t);
?????? if(s==t)
????? {printf("0\n");continue;}

??????? b[s]=1;
??????? m=n-1;
??????? while(m--)
??????? {
?????????? min=0x7ffffff;
?????????? for(i=0;i<n;i++)
???????????? if(!b[i]&&p[s][i]<min)
???????????? {
???????????????? min=p[s][i];
????????????????? j=i;
???????????? }
??????????? if(min==0x7ffffff)
?????????????? break;
??????????? b[j]=1;
??????? for(i=0;i<n;i++)
?????????? if(!b[i]&&p[s][j]+p[j][i]<p[s][i])
???????????? p[s][i]=p[s][j]+p[j][i];
??????? }
??????? if(p[s][t]==0x7ffffff)//開始這里就錯了，判斷成所有點都得連通，Prim做傻了、、
??????? printf("-1\n");
??????? else
??????? printf("%d\n",p[s][t]);
??? }
??? return 0;
}

轉載于:https://www.cnblogs.com/372465774y/archive/2012/04/04/2432096.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的HDU 1874 畅通工程续的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。