HDU 1596：find the safest road【Dijkstra & SPFA】

find the safest road
Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 9078    Accepted Submission(s): 3191
Problem Description
XX 별 에는 많은 도시 가 있 습 니 다.도시 마다 하나 이상 의 비행 통로 가 있 습 니 다.그러나 모든 길이 안전 한 것 은 아 닙 니 다.모든 길 에는 안전 계수 s 가 있 습 니 다.s 는 0 과 1 칸 의 실수(0,1 포함)입 니 다.u 에서 v 까지 의 통로 P 의 안전 도 는 Safe(P)=s(e1)*s(e2)...*s(ek)e1,e2,ek 는 P 의 가장자리 입 니 다.지금 8600 은 여행 을 가 고 싶 습 니 다.이렇게 많은 길 을 마주 하고 그 는 가장 안전 한 길 을 찾 으 려 고 한다.하지만 8600 은 수학 을 잘 못 해 요.도와 주 고 싶 어 요^ ^
 
Input
여러 개의 테스트 인 스 턴 스 를 포함 하여 입력 하 십시오.모든 인 스 턴 스 는 다음 을 포함 합 니 다.
첫 줄n 도시 의 개수 n<=1000;
이 어 n*n 의 행렬 은 두 도시 간 의 안전 계 수 를 나타 낸다.(0 은 그 두 도시 사이 에 직접적인 통로 가 없다 고 이해 할 수 있다)
이 어 8600 개 여행 코스 Q 개 로 줄 당 두 개의 숫자 가 있 으 며 8600 이 있 는 도시 와 가 야 할 도 시 를 나타 낸다.
 
Output
86 이 그의 목적지 에 도달 하지 못 하면"What a pity!"를 출력 합 니 다.
다른 수출 두 도시 간 의 가장 안전 한 도로 의 안전 계 수 는 세 개의 소 수 를 유지한다.
 
Sample Input

   
   
   
   

    
    
    
    3
1 0.5 0.5
0.5 1 0.4
0.5 0.4 1
3
1 2
2 3
1 3
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    0.500
0.400
0.500
   
   
   
   

 
AC-code:
Dijkstra:

#include<cstdio>
#define min(a,b) (a>b?a:b)
int n;
float cost[1005][1005],dis[1005];
void dijkstra(int a)
{
	int i,vis[1005];
	for(i=1;i<=n;i++)
	{
		dis[i]=0;
		vis[i]=0;
	}
	dis[a]=1;
	while(1)
	{
		int v=-1;
		for(i=1;i<=n;i++)
			if(!vis[i]&&(v==-1||dis[i]>dis[v]))
				v=i;
		if(v==-1)
			break;
		vis[v]=1;
		for(i=1;i<=n;i++)
			dis[i]=min(dis[i],dis[v]*cost[v][i]);
	}
}
int main()
{
	int q,i,j,a,b;
	while(~scanf("%d",&n))
	{
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				scanf("%f",&cost[i][j]);
		scanf("%d",&q);
		while(q--)
		{
			scanf("%d%d",&a,&b);
			dijkstra(a);
			if(dis[b]==0)
				printf("What a pity!
");
			else
				printf("%.3lf
",dis[b]);
		}
	}
	return 0;
}

 SPFA:

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
float vis[1005],dis[1005];
int head[1000*1000],nu;
struct node
{
	int from,to;
	float val;
	int next;
}A[1000*1000];

void chan(int a,int b,float c)
{
	node e={a,b,c,head[a]};
	A[nu]=e;
	head[a]=nu++;
}
void spfa(int sx)
{
	queue<int>q;
	memset(dis,0,sizeof(dis));
	memset(vis,0,sizeof(vis));
	q.push(sx);
	dis[sx]=1;
	vis[sx]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i!=-1;i=A[i].next)
		{
			int v=A[i].to;
			if(dis[v]<dis[u]*A[i].val)
			{
				dis[v]=dis[u]*A[i].val;
				if(!vis[v])
				{
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
}
int main()
{
	int n,i,j,q,b,c;
	float a;
	while(~scanf("%d",&n))
	{
		nu=0;
		memset(head,-1,sizeof(head));
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
			{
				scanf("%f",&a);
				chan(i,j,a);
			}
		scanf("%d",&q);
		while(q--)
		{
			scanf("%d%d",&b,&c);
			spfa(b);
			if(dis[c]==0)
				printf("What a pity!
");
			else
				printf("%.3f
",dis[c]);
		}
	}
	return 0;
}