城市平乱
时间限制：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<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
using namespace std;
const int maxn=;
const int inf=0x3f3f3f3f;
int cost[maxn][maxn];
int path[maxn],lowc[maxn];
bool vis[maxn];
void Dijkstra(int n,int st)
{
int i,j,minc;
memset(vis,,sizeof(vis));
vis[st]= ;
for(i=;i<n;i++)
{
lowc[i]=cost[st][i];
path[i]=st;
}
lowc[st]=;
path[st]=-; //树根的标记
int pre=st;
for(i=;i<n;i++)
{
minc=inf;
for(j=;j<n;j++)
{
if(vis[j]==&&lowc[pre]+cost[pre][j]<lowc[j])
{
lowc[j]=lowc[pre]+cost[pre][j];
path[j]=pre;
}
}
for(j=;j<n;j++)
{
if(vis[j]==&&lowc[j]<minc)
{
minc=lowc[j];
pre=j;
}
}
vis[pre]=;
}
}
int groop[];
int main()
{
int n,m,p,q,i,j;
int a,b,c,test,res;
// freopen("test.in","r",stdin);
scanf("%d",&test);
while(test--)
{
scanf("%d%d%d%d",&n,&m,&p,&q);
for(i=;i<n;i++)
scanf("%d",&groop[i]);
for(i=;i<m;i++)
for(j=;j<m;j++)
cost[i][j]=inf;
for(i=;i<p;i++)
{
scanf("%d%d%d",&a,&b,&c);
a-- , b-- ;
if(cost[a][b]>c||cost[a][b]==)
cost[a][b]=cost[b][a]=c;
}
Dijkstra(m,q-);
res=inf;
for(i=;i<n;i++)
{
if(res>lowc[groop[i]-])
res=lowc[groop[i]-];
}
printf("%d\n",res);
}
return ;
}采用bellman算法求最短路 裸的算法
代码：
/*bellman求最短路*/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
using namespace std; const int inf=0x3f3f3f3f;
int m,n,p,q,pre[],edge[][];
int dist[]; int relax(int u ,int v ,int c)
{
if(dist[v]>dist[u]+c)
{
dist[v]=dist[u]+c;
pre[v]=u;
return ;
}
return ;
} int bellman(int st)
{
int i,j;
for(i=;i<=m;i++){
dist[i]=inf;
pre[i]=-;
}
dist[st]=;
bool flag;
for(i=;i<m;i++)
{
flag=false; //优化
for(j=;j<=*p;j++)
{
if(==relax(edge[j][],edge[j][],edge[j][]))
flag=true;
}
if(!flag) break;
}
for(j=;j<=*p;j++)
{
if(==relax(edge[j][],edge[j][],edge[j][]))
return ; //有负圈
}
return ;
}
int groop[];
int main()
{
int test,i,j;
// freopen("test.in","r",stdin);
scanf("%d",&test);
while(test--)
{
scanf("%d%d%d%d",&n,&m,&p,&q);
for(i=;i<n;i++)
scanf("%d",&groop[i]);
for(i=;i<=p;i++)
{
//建立无向图
scanf("%d%d%d",&edge[i][],&edge[i][],&edge[i][]);
edge[p+i][]=edge[i][];
edge[p+i][]=edge[i][];
edge[p+i][]=edge[i][];
}
bellman(q);
int res=inf;
for(i=;i<n;i++)
{
if(res>dist[groop[i]])
res=dist[groop[i]];
}
printf("%d\n",res);
}
return ;
} - 采用bellman优化的算法即SPFA进行求解：
- 代码如下：
- 套用模板居然错了，还有比这更扯的嘛!!!
- 邻接表+狄斯喹诺算法
- RuntimeError
-
/*狄斯喹诺算法*/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#pragma comment(linker, "/STACK:102400000,102400000") const int inf=0x3f3f3f3f;
using namespace std ; int cost[],dist[];
int e,pnt[],next[],head[],prev[],vis[];
int groop[]; struct node
{
int v,c;
node ( int vv= , int cc= ) : v(vv),c(cc){}
bool operator < ( const node &r ) const
{
return c>r.c ;
}
}; void dijkstra (int n ,const int src)
{
node mv;
int i,j,k,pre;
priority_queue<node> que;
vis[src]=;
dist[src]=;
que.push(node(src,));
for(pre=src,i=;i<n;i++)
{
for(j=head[pre];j!=-;j=next[j])
{
k=pnt[j];
if(vis[k]==&&dist[pre]+cost[j]<dist[k])
{
dist[k]=dist[pre]+cost[k];
que.push(node(pnt[j] , dist[k]));
prev[k]=pre;
}
} while(!que.empty()&&vis[que.top().v]==)
que.pop();
if(que.empty()) break;
mv=que.top();
que.pop();
vis[mv.v]=;
pre=mv.v; }
} inline void addedge(int u , int v , int c)
{
//面对重边又该怎么办 pnt[e]=v;
cost[e]=c;
next[e]=head[u];
head[u]=e++;
} void init(int nv ,int ne)
{
int i,u,v,c;
e=;
memset( head , - , sizeof(head) );
memset( vis , , sizeof(vis) );
memset( prev , - , sizeof(prev) );
memset(pnt,,sizeof(pnt));
for(i=;i<nv;i++)
dist[i]=inf;
// 如 何 应 对 重 边
for(i=;i<ne;i++)
{
scanf("%d%d%d",&u,&v,&c);
u-- ;
v-- ;
addedge(u,v,c);
addedge(v,u,c);
}
} int main()
{
int test,i;
int n,m,p,q;
scanf("%d",&test);
while(test--)
{
memset(cost,-,sizeof(cost));
scanf("%d%d%d%d",&n,&m,&p,&q);
for(i=;i<n;i++)
scanf("%d",&groop[i]);
init(p,p);
dijkstra(n,q-);
int res=inf;
for(i=;i<n;i++)
if(res>dist[groop[i]-])
res=dist[groop[i]-];
printf("%d\n",res);
}
return ;
}