信道安全
时间限制：1000 ms | 内存限制：65535 KB
难度：2
- 描述
- Alpha 机构有自己的一套网络系统进行信息传送。情报员 A 位于节点 1，他准备将一份情报 发送给位于节点 n 的情报部门。可是由于最近国际纷争，战事不断，很多信道都有可能被遭到监 视或破坏。 经过测试分析，Alpha 情报系统获得了网络中每段信道安全可靠性的概率，情报员 A 决定选 择一条安全性最高，即概率最大的信道路径进行发送情报。 你能帮情报员 A 找到这条信道路径吗？
- 输入
- 第一行： T 表示以下有 T 组测试数据 （ 1≤T ≤8 ）
对每组测试数据：
第一行：n m 分别表示网络中的节点数和信道数 (1<=n<=10000，1<=m<=50000)
接下来有 m 行， 每行包含三个整数 i，j，p，表示节点 i 与节点 j 之间有一条信道，其信
道安全可靠性的概率为 p%。 ( 1<=i, j<=n 1<=p<=100) - 输出
- 每组测试数据，输出占一行，一个实数 即情报传送到达节点 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 spfa模板题，记得vector清空，错了2发，哭了TwT
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define lrt (rt*2)
#define rrt (rt*2+1)
#define LL long long
#define inf 0x3f3f3f3f
#define pi acos(-1.0)
#define exp 1e-8
//*************************************************** #define eps 1e-8
#define inf 0x3f3f3f3f
#define INF 2e18
#define LL long long
#define ULL unsigned long long
#define PI acos(-1.0)
#define pb push_back
#define mk make_pair #define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define SQR(a) ((a)*(a))
#define Unique(a) sort(all(a)),a.erase(unique(all(a)),a.end())
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define max4(a,b,c,d) max(max(a,b),max(c,d))
#define max5(a,b,c,d,e) max(max3(a,b,c),max(d,e))
#define min5(a,b,c,d,e) min(min3(a,b,c),min(d,e))
#define Iterator(a) __typeof__(a.begin())
#define rIterator(a) __typeof__(a.rbegin())
#define FastRead ios_base::sync_with_stdio(0);cin.tie(0)
#define CasePrint pc('C'); pc('a'); pc('s'); pc('e'); pc(' '); write(qq++,false); pc(':'); pc(' ')
#define vi vector <int>
#define vL vector <LL>
#define For(I,A,B) for(int I = (A); I < (B); ++I)
#define FOR(I,A,B) for(int I = (A); I <= (B); ++I)
#define rFor(I,A,B) for(int I = (A); I >= (B); --I)
#define Rep(I,N) For(I,0,N)
#define REP(I,N) FOR(I,1,N)
#define mem(A, val) memset(A,val,sizeof(A))
const int M=*;
using namespace std;
const int maxn=1e4+;
const int MOD=1e9+;
int m,n;
struct Edge
{
int v;
double cost;
Edge(int vv=,double ccost=0.0):v(vv),cost(ccost){}
};
bool vis[maxn];
double dis[maxn];
int cnt[maxn];
vector<Edge>E[M];
bool spfa()
{
memset(vis,false,sizeof(vis));
// memset(vis,false,sizeof(vis));
for(int i=;i<=m;i++) dis[i]=-*inf;
vis[]=true; dis[]=1.0;
queue<int>que;
while(!que.empty()) que.pop();
que.push();
memset(cnt,,sizeof(cnt));
cnt[]=;
while(!que.empty())
{
int u=que.front();
que.pop();
vis[u]=false;
for(int i=;i<E[u].size();i++)
{
int v=E[u][i].v;
if(dis[v]<dis[u]*E[u][i].cost)
{
dis[v]=dis[u]*E[u][i].cost;
if(!vis[v])
{
vis[v]=true;
que.push(v);
if(++cnt[v]>m) return false;
}
}
}
}
return true;
}
void add(int u,int v,int w)
{
E[u].push_back(Edge(v,w/100.0));
}
int main()
{
int t,x,y,z;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&m,&n);
for(int i=;i<=m;i++)
E[i].clear();
for(int i=;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
spfa();
printf("%.6f\n",dis[m]*);
}
return ;
}