hdu1596——find the safest road

find the safest road
Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 7275    Accepted Submission(s): 2580
Problem Description
XX星には多くの都市があり、各都市の間には1つ以上の飛行通路がありますが、すべての道が安全であるわけではありません.各道路には安全係数sがあり、sは0と1の間の実数(0,1を含む)で、uからvまでの通路Pの安全度はSafe(P)=s(e 1)*s(e 2)…*s(ek)e 1、e 2、ekはPの端で、今8600は旅行に行きたいと思っています.このような多くの道に直面して、彼は最も安全な道を探したいと思っています.でも8600は数学が苦手なので手伝ってもらいたいです^^;
 
Input
入力には、次のような複数のテストインスタンスが含まれます.
1行目:n.nは都市の個数n<=1000を表す.
次にn*nの行列が2つの都市間の安全係数を表す(0はその2つの都市間に直接的な通路がないと理解できる)
続いてQつの8600の旅行するルートで、1行ごとに2つの数字があって、8600の所在する都市と行く都市を表します
 
Output
86が目的地に達しなければ「What a pity!」と出力し、
他の出力の2つの都市間の最も安全な道路の安全係数は、3桁の小数を保持します.
 
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
   
   
   
   

 
Author

#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

struct node
{
	double weight;
	int next;
	int to;
}edge[N * N];

double dist[N];
int head[N];
int tot, n;

void addedge(int from, int to, double weight)
{
	edge[tot].weight = weight;
	edge[tot].to = to;
	edge[tot].next = head[from];
	head[from] = tot++;
}

void spfa(int v0)
{
	for (int i = 1; i <= n; i++)
	{
		dist[i] = 0.000;
	}
	dist[v0] = 1.000;
	queue <int> qu;
	while ( !qu.empty() )
	{
		qu.pop();
	}
	qu.push(v0);
	while ( !qu.empty() )
	{
		int u = qu.front();
		qu.pop();
		for (int i = head[u]; ~i; i = edge[i].next)
		{
			int v = edge[i].to;
//			printf("%.3f %.3f
", dist[v], dist[u] * edge[i].weight);
			if (dist[v] < dist[u] * edge[i].weight)
			{
				dist[v] = dist[u] * edge[i].weight;
				qu.push(v);
			}
		}
	}
}

int main()
{
	while (~scanf("%d", &n))
	{
		double w;
		int u, v;
		memset (head, -1, sizeof(head) );
		tot = 0;
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				scanf("%lf", &w);
				addedge(i, j, w);
			}
		}
		int m;
		scanf("%d", &m);
		while (m--)
		{
			scanf("%d%d", &u, &v);
			spfa(u);
			if (dist[v] != 0)
			{
				printf("%.3lf
", dist[v]);
				continue;
			}
			printf("What a pity!
");
		}
	}
	return 0;
}

ailyanlu
 
Source
HDU 2007-Spring Programming Contest - Warm Up (1)
 
Recommend
8600   |   We have carefully selected several similar problems for you:   1217  1598  1142  1690  2544 
 
最短の変形、 制限条件を改めればよい