城市平乱
时间限制：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 MIN(x,y)(x<y?x:y)
#define mem(x,y) memset(x,y,sizeof(x))
const int INF=0x3f3f3f3f;
const int MAXN=;
const int MAXM=<<;
int N,M,P,Q;
int em;
int dis[MAXN],st[MAXN];
struct Node{
int u,v,w;
};
Node dt[MAXM];
void add(int u,int v,int w){
dt[em].u=u;dt[em].v=v;dt[em++].w=w;
}
void Bellman(int sx){
mem(dis,INF);
dis[sx]=;
for(int i=;i<=M;i++){
for(int j=;j<em;j++){
int u=dt[j].u,v=dt[j].v,w=dt[j].w;
dis[v]=MIN(dis[v],dis[u]+w);
}
}
}
int main(){
int T,a,b,c;
scanf("%d",&T);
while(T--){
em=;
scanf("%d%d%d%d",&N,&M,&P,&Q);
for(int i=;i<N;i++)scanf("%d",st+i);
while(P--){
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
int ans=INF;
Bellman(Q);
for(int i=;i<N;i++){
ans=MIN(ans,dis[st[i]]);
}
printf("%d\n",ans);
}
return ;
}