Dijkstra/Floyd-Warshall 最短路径算法

描述

南将军统领着N个部队，这N个部队分别驻扎在N个不同的城市。

他在用这N个部队维护着M个城市的治安，这M个城市分别编号从1到M。

现在，小工军师告诉南将军，第K号城市发生了*，南将军从各个部队都派遣了一个分队沿最近路去往*城市平乱。

现在已知在任意两个城市之间的路行军所需的时间，你作为南将军麾下最厉害的程序员，请你编写一个程序来告诉南将军第一个分队到达*城市所需的时间。

注意，两个城市之间可能不只一条路。

 

输入

第一行输入一个整数T，表示测试数据的组数。(T<20)
每组测试数据的第一行是四个整数N,M,P,Q(1<=N<=100,N<=M<=1000,M-1<=P<=100000)其中N表示部队数，M表示城市数，P表示城市之间的路的条数,Q表示发生*的城市编号。
随后的一行是N个整数，表示部队所在城市的编号。
再之后的P行，每行有三个正整数，a,b,t(1<=a,b<=M,1<=t<=100)，表示a,b之间的路如果行军需要用时为t

数据保证*的城市是可达的。

输出

对于每组测试数据，输出第一支部队到达*城市时的时间。每组输出占一行

样例输入

1
3 8 9 8
1 2 3
1 2 1
2 3 2
1 4 2
2 5 3
3 6 2
4 7 1
5 7 3
5 8 2
6 8 2 

样例输出

4

 

#include <stdio.h>#include <stdlib.h>#include <iostream>#include <string.h>using namespace std;bool Visited[1005];int Distance[1005];int ArmRec[105],DisRec[1005][1005];int NumOfArmy,NumOfCity,NumOfRoad,NumDest;#define FALSE 0#define TRUE 1void UpdateDis(int start){int i; for (i=1;i<=NumOfCity;i++){if (Visited[i]==FALSE&&DisRec[start][i]!=0&&(DisRec[start][i]+Distance[start]<Distance[i]))Distance[i]=DisRec[start][i]+Distance[start];}}int GetMin(){ int i,smin,sminpos;for (i=1;i<=NumOfCity;i++)if (Visited[i]==FALSE){ smin=Distance[i]; sminpos=i; break;}for (i=1;i<=NumOfCity;i++){if (Visited[i]==FALSE&&Distance[i]<smin){smin=Distance[i];sminpos=i;break;}}return sminpos;}void InitTable(int start){ int i;for (i=1;i<=1004;i++) Distance[i]=999999;for (i=1;i<=NumOfCity;i++){if (DisRec[start][i]!=0){ Distance[i]=DisRec[start][i];}}}int main(){ int t,i,a,b,lt,vcount,curmin,minlen;//freopen("E://input.txt","r",stdin); scanf("%d",&t);while (t--){scanf("%d%d%d%d",&NumOfArmy,&NumOfCity,&NumOfRoad,&NumDest);memset(DisRec,0,sizeof(DisRec)); for (i=1;i<=NumOfArmy;i++) scanf("%d",&ArmRec[i]);for (i=1;i<=NumOfRoad;i++){scanf("%d%d%d",&a,&b,<);if (DisRec[a][b]==0||lt<DisRec[a][b]){ DisRec[a][b]=lt; DisRec[b][a]=lt;}}minlen=999999;for (i=1;i<=NumOfArmy;i++){ memset(Visited,FALSE,sizeof(Visited));vcount=1;InitTable(ArmRec[i]);Visited[ArmRec[i]]=TRUE;while (vcount<NumOfCity){curmin=GetMin(); UpdateDis(curmin);Visited[curmin]=TRUE; vcount++;}if (Distance[NumDest]<minlen)minlen=Distance[NumDest];}printf("%d/n",minlen);} return 0;}

 

#include <stdio.h>#include <stdlib.h>#include <iostream>#include <string.h>#include <math.h>using namespace std;int len[1005][1005];int main(){int t,i,j,k,a,b,lt,smin;int NumOfArmy,NumOfCity,NumOfRoad,NumDest;int ArmRec[105];//freopen("E://Input.txt","r",stdin);scanf("%d",&t); while (t--){for (i=0;i<1005;i++)for (j=0;j<1005;j++) len[i][j]=1000000; scanf("%d%d%d%d",&NumOfArmy,&NumOfCity,&NumOfRoad,&NumDest); for (i=1;i<=NumOfArmy;i++) scanf("%d",&ArmRec[i]);for (i=0;i<NumOfRoad;i++){scanf("%d%d%d",&a,&b,<);if (lt<len[a][b]){len[a][b]=lt; len[b][a]=lt;}}for (k=1;k<=NumOfCity;k++)for (i=1;i<=NumOfCity;i++)for (j=1;j<=NumOfCity;j++) if (len[i][j]>len[i][k]+len[k][j]) len[i][j]=len[i][k]+len[k][j]; smin=1000000;for (i=1;i<=NumOfArmy;i++) if (len[ArmRec[i]][NumDest]<smin)smin=len[ArmRec[i]][NumDest];printf("%d/n",smin);} return 0;}