TOJ 3692:紧急援救最短路 dijstra

快来打我* 2022-05-27 09:55 230阅读 0赞

描述

人质被恐怖分子扣押，幸好警察已经在一些路口准备好警车随时出动，救援马上开始...  
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

样例输出

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");
    		else
    		printf("%.2lf\n",mint);
    		printf("\n");
    	}
    }