nyoj 115 城市平亂

城市平亂

時間限制： 1000 ms  |  記憶體限制： 65535 KB 難度： 4

描述

南将軍統領着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<string.h>
#include<stdlib.h>
#include<math.h>
#define  inf 100000000
#define  ac 1100
int map[ac][ac],dist[ac],visit[ac],s[ac];
int army,city,road,fire,start;
int dijkstra(int start)
{
	int mindist,next;
	int i,j;
	memset(visit,0,sizeof(visit));
	for(i=1;i<=city;i++)
	{
		dist[i]=map[start][i];
	}
	visit[start]=1;
	for(i=2;i<=city;i++)
	  {
	  	mindist=inf;
	  	for(j=1;j<=city;j++)
	  	 {
	  	 	if(visit[j]==0&&dist[j]<mindist)
	  	 	{
	  	 		mindist=dist[j];
	  	 		next=j;
			}	
		 }
		 visit[next]=1;
		 for(j=1;j<=city;j++)
		 {
		 	if(visit[j]==0&&dist[next]+map[next][j]<dist[j])
		 	dist[j]=dist[next]+map[next][j];
		 }
	  }
	  return dist[fire];
}
int main()
{
	int a,n,b,t,m;
	int i,j;
	int dis[1100];
	scanf("%d",&n);
	while(n--)
	{
		scanf("%d%d%d%d",&army,&city,&road,&fire);
		 for(i=1;i<=city;i++)
		  for(j=1;j<=city;j++)
		      {
		      	map[i][j]=inf;
		      	if(i==j)
		      	 map[i][j]=0;
			  }
		  for(i=1;i<=army;i++)
		   {
		   	scanf("%d",&s[i]);
		   }
	      for(i=1;i<=road;i++)
	       {
	       	scanf("%d%d%d",&a,&b,&t);
	       	if(map[a][b]>t)
	       	map[a][b]=map[b][a]=t;
		   }
		  for(i=1;i<=army;i++)
		   {
		     dis[i]=dijkstra(s[i]);//将每個部隊用的時間存儲起來！ 
	       }
	       m=inf;
	      for(i=1;i<=army;i++)//進行一一比較！ 
	       {
	       	  if(dis[i]<m)
	       	  {
	       	  	m=dis[i];
			  }
		   }
		   printf("%d\n",m);
    }
}