城市平亂

時(shí)間限制：1000?ms ?|? 內(nèi)存限制：65535?KB 難度：4 描述

南將軍統(tǒng)領(lǐng)著N個(gè)部隊(duì)，這N個(gè)部隊(duì)分別駐扎在N個(gè)不同的城市。

他在用這N個(gè)部隊(duì)維護(hù)著M個(gè)城市的治安，這M個(gè)城市分別編號從1到M。

現(xiàn)在，小工軍師告訴南將軍，第K號城市發(fā)生了暴亂，南將軍從各個(gè)部隊(duì)都派遣了一個(gè)分隊(duì)沿最近路去往暴亂城市平亂。

現(xiàn)在已知在任意兩個(gè)城市之間的路行軍所需的時(shí)間，你作為南將軍麾下最厲害的程序員，請你編寫一個(gè)程序來告訴南將軍第一個(gè)分隊(duì)到達(dá)叛亂城市所需的時(shí)間。

注意，兩個(gè)城市之間可能不只一條路。

輸入

第一行輸入一個(gè)整數(shù)T，表示測試數(shù)據(jù)的組數(shù)。(T<20)
每組測試數(shù)據(jù)的第一行是四個(gè)整數(shù)N,M,P,Q(1<=N<=100,N<=M<=1000,M-1<=P<=100000)其中N表示部隊(duì)數(shù)，M表示城市數(shù)，P表示城市之間的路的條數(shù),Q表示發(fā)生暴亂的城市編號。
隨后的一行是N個(gè)整數(shù)，表示部隊(duì)所在城市的編號。
再之后的P行，每行有三個(gè)正整數(shù)，a,b,t(1<=a,b<=M,1<=t<=100)，表示a,b之間的路如果行軍需要用時(shí)為t

數(shù)據(jù)保證暴亂的城市是可達(dá)的。

輸出

對于每組測試數(shù)據(jù)，輸出第一支部隊(duì)到達(dá)叛亂城市時(shí)的時(shí)間。每組輸出占一行

樣例輸入

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

應(yīng)用Dijkstra算法求解！

AC碼：

#include<stdio.h> #include<string.h> #define INF 999999999 int G[1010][1010],visit[1010],dist[1010]; int main() {int T,n,m,p,q,a,b,t,min,i,j,k;int army[105];scanf("%d",&T);while(T--){scanf("%d%d%d%d",&n,&m,&p,&q);// 輸入軍隊(duì)所在的頂點(diǎn)for(i=0;i<n;i++)scanf("%d",&army[i]);// 初始化鄰接矩陣for(i=0;i<=m;i++){for(j=0;j<=m;j++)G[i][j]=INF;}// 輸入可行的路徑及所需時(shí)間for(i=0;i<p;i++){scanf("%d%d%d",&a,&b,&t);G[a][b]=G[b][a]=t; // 創(chuàng)建鄰接矩陣}// Dijkstra算法求出源點(diǎn)q到其他各個(gè)頂點(diǎn)的最短路徑長度memset(visit,0,sizeof(visit));for(i=1;i<=m;i++)dist[i]=G[q][i]; // 初始化distvisit[q]=1;for(i=1;i<=m;i++){min=INF;for(j=1;j<=m;j++){if(!visit[j]&&min>dist[j]){min=dist[j];k=j;}}visit[k]=1;if(min==INF)break;for(j=1;j<=m;j++){if(!visit[j]&&dist[j]>min+G[k][j])dist[j]=min+G[k][j];}}// 找出軍隊(duì)所在頂點(diǎn)到源點(diǎn)的最小時(shí)間min=INF;for(i=0;i<n;i++){if(min>dist[army[i]])min=dist[army[i]];}printf("%d\n",min);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的NYOJ 115 城市平乱的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。