nyoj 1274&&河南省第9回ACMコンテストC題

チャネルセキュリティ
時間制限:
1000 ms|メモリ制限:
65535 KB
難易度:
2
説明
Alpha機構は独自のネットワークシステムを持って情報伝送を行う.情報員Aはノード1に位置し、ノードnにある情報部門に情報を送信する準備をしている.しかし、最近の国際紛争で戦争が絶えず、多くのチャネルが監視されたり破壊されたりする可能性がある.試験分析により、Alpha情報システムは、ネットワーク内の各セグメントのチャネルセキュリティ信頼性の確率を取得し、情報員Aは、最も安全性の高い、すなわち最も確率の高いチャネル経路を選択して情報を送信することを決定する.情報員Aにこのチャネルパスを見つけてもらえますか? 
入力
1行目:Tは以下のT組のテストデータを表す(1≦T≦8)
各テストデータのセット:
第1行:nmは、ネットワーク内のノード数およびチャネル数をそれぞれ表す(1<=n<=10000、1<=m<=50000)
次にm行があり、各行は3つの整数i,j,pを含み、ノードiとノードjとの間に1つのチャネルがあり、その信号を表す
チャネル安全信頼性の確率はp%であった.( 1<=i, j<=n 1<=p<=100)
しゅつりょく
各グループのテストデータは、出力が1行を占め、1つの実数、すなわち情報がノードnに伝達される最高確率は、小数点以下に正確である.
6名様です.
サンプル入力

1
5 7
5 2 100
3 5 80
2 3 70
2 1 50
3 4 90
4 1 85
3 1 70

サンプル出力

61.200000 

1本の比较的に简単な问题、试合の前に私の主攻の方向は図论ではありませんて、だからこの学の比较的に浅くて、ただいくつかの比较的によく使う简単なアルゴリズムを学んで、この问题はチームメートが书いたので、それからまたこのアルゴリズムを学んで、感じはとても简単で、ただ理解するのは特に容易ではないかもしれません;ここでは、疎図の隣接表という文章を見ることをお勧めします.よく話していますが、私もこれを見て理解しました.
解題構想:直接最短ルートの中で、隣接表+キューというアルゴリズムを適用して、ただ最短ルートを求めることを酔っ払う長い道を求めることに変えて、それから道路権の処理に注意します

    ：
#include 
#include 
using namespace std;
struct Node
{
	int to,next;
	double w;
}edge[50005*2];
int head[10005];
int used[10005];
double dist[10005];
int num,n,m;
void add(int u,int v,int e)
{
	edge[num].to=v;
	edge[num].w=(double)e/100;
	edge[num].next=head[u];
	head[u]=num++;
}
void Spfa(int star)
{
	int u,v,i;
	queue Q;
	for(i=1;i<=n;i++)
		dist[i]=0;
	dist[star]=1;
	used[star]=1;
	Q.push(star);
	while(!Q.empty())
	{
		u=Q.front();
		Q.pop();
		used[u]=0;
		for(i=head[u];i!=-1;i=edge[i].next)
		{
			v=edge[i].to;
			if(dist[v]