暢通工程續 Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 19131 Accepted Submission(s): 6616 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 #include <iostream> #define INF 9999999 using namespace std; int main (void) { int n,m,s,d,a,b,x,i,j,k,l,line[222],over[222],ss[222][222]; while(cin>>n>>m) { for(i=0;i<n;i++) for(j=0;j<n;j++) ss[i][j]=INF; //路數組數組初始化，含義為從起點到此點距離無窮大* for(i=0;i<m;i++) { cin>>a>>b>>x; if(ss[a][b]>x)ss[a][b]=ss[b][a]=x; //可能有重復路不同距離 } cin>>s>>d; for(i=0;i<222;i++) line[i]=INF,over[i]=1;line[s]=0; //路線距離、最近點標記數組初始化，起點路線距離為0 for(i=0;i<n;i++) //n次循環 { k=INF;l=s; for(j=0;j<n;j++) //找出當前從起點到最近的未標記點 if(over[j]&&k>line[j])k=line[l=j]; over[l]=0; //此點標記 for(j=0;j<n;j++) //從路數組裡面看有沒有從標記點到達的比起點到達距離更小的點 if(line[j]>line[l]+ss[l][j]) line[j]=line[l]+ss[l][j]; } if(line[d]==INF)cout<<"-1"<<endl; else cout<<line[d]<<endl; } return 0; }
