城市平乱
时间限制：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>
#define inf 0xfffff int g[][];
int lowcost[],used[]; void dijskra(int n,int a)
{
int i,j,k,min;
memset(used,,sizeof(used));
memset(lowcost,,sizeof(lowcost));
for(i=;i<=n;i++)
lowcost[i]=g[i][a];
used[a]=;
for(i=;i<n;i++)
{
j=a;
min=inf;
for(k=;k<=n;k++)
{
if(lowcost[k]<min&&!used[k])
{
min=lowcost[k];
j=k;
}
}
used[j]=;
for(k=;k<=n;k++)
{
if(lowcost[j]+g[k][j]<lowcost[k]&&!used[k])
lowcost[k]=lowcost[j]+g[k][j],
g[k][a]=g[a][k]=lowcost[k];
}
}
} int main()
{
int n,m,p,q,i,j,t;
int army;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d%d",&n,&m,&p,&q);
for(i=;i<=m+;i++)
{
for(j=;j<=m+;j++)
{
g[i][j]=inf;
}
g[i][i]=;
}
for(i=;i<n;i++)
{
scanf("%d",&army);
g[army][m+]=g[m+][army]=;
}
for(i=;i<p;i++)
{
int a,b,t;
scanf("%d%d%d",&a,&b,&t);
g[a][b]=g[b][a]=t;
}
dijskra(m+,m+);
printf("%d\n",g[q][m+]);
}
}