本文主要是介绍TOJ 3692:紧急援救 最短路 dijstra，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
描述
人质被恐怖分子扣押，幸好警察已经在一些路口准备好警车随时出动，救援马上开始...
zzzz，稍安勿躁，警察需要以最少的时间到达案发现场，那应该出动哪辆警车呢？这辆警车最快需要多少时间能够到达现场呢？又幸好警方最近聘请了一位编程高手，那就是你，现在请你马上编写程序来实现。
输入
输入数据的第一行为3个整数n（n<=1000）、m（m<=10000）和s，其中n表示路口的数目，分别从1到n进行编号，m表示马路的条数，s表示案发次数。
接下来有m行，每行表示一条马路信息，每条马路信息包含起点s（路口编号）、终点e（路口编号）以及从s到e所需要的时间t，其中1<=s,e<=n，t为一个非负实数。
接下来包含s个案件，每个案件有两行，第一行为两个正整数c和k，c表示案发现场（路口编号），k表示警车的数目，第二行有k个正整数，每个正整数对应一个警车所在的路口编号。
输出
对每个案件，第一行输出：
Scenario x:
其中x表示案件的编号，从1开始。
第二行输出最快到达的时间，保留2位小数，如果无法到达则输出：
Impossible.
每个案件之后再输一个空行。
样例输入
6 9 2
1 2 3.5
1 3 1.2
3 4 4.9
2 4 0.221
5 4 0.1
5 6 1.3
4 6 1
2 3 0
3 2 5
4 2
1 3
5 1
6
样例输出
Scenario 1:
3.72
Scenario 2:
Impossible.
一开始用深搜写的超时了...委屈巴巴... 还是乖乖用dijstra吧。。。
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
using namespace std;//3692
#define inf 0x3f3f3f3f
int k,n;
double ma[1005][1005],vis[1005],dis[1005];
double minPath;
void dijstra(int begin)
{memset(vis,0,sizeof vis);int i,j,k,mi,temp;for(i=1;i<=n;i++)dis[i]=ma[begin][i];dis[begin]=0;vis[begin]=1;for(i=1;i<=n;i++){mi=inf;for(j=1;j<=n;j++){if(!vis[j]&&dis[j]<mi){mi=dis[j];temp=j;}}if(mi==inf)break;vis[temp]=1;for(k=1;k<=n;k++){if(!vis[k]&&dis[k]>dis[temp]+ma[temp][k])dis[k]=dis[temp]+ma[temp][k];}}
}
int main()
{int m,i,j,t,x,y,ts,beg;double z;scanf("%d%d%d",&n,&m,&t);for(i=1;i<=n;i++){for(j=1;j<=n;j++)ma[i][j]=inf;}for(i=0;i<m;i++){scanf("%d%d%lf",&x,&y,&z);if(ma[x][y]>z)ma[x][y]=z;}for(i=1;i<=t;i++){double mint=inf;scanf("%d%d",&k,&ts);for(j=0;j<ts;j++){ scanf("%d",&beg);dijstra(beg);if(dis[k]<mint)mint=dis[k]; } printf("Scenario %d:\n",i);if(mint==inf)printf("Impossible.\n");elseprintf("%.2lf\n",mint);printf("\n");}
}
这篇关于TOJ 3692:紧急援救 最短路 dijstra的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
