题目链接:http://nyoj.top/problem/1274

  • 内存限制:64MB 时间限制:1000ms

题目描述

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

解题思路

最短路变形。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e4 + 5;
struct edge {
    int u, v, w;
}e[5 * MAXN];
double dis[MAXN];
int f[MAXN], vis[MAXN], cnt;
void Add(int u, int v, int w) {
    e[++cnt] = (edge){f[u], v, w};
    f[u] = cnt;
}
void Spfa(int s) {
    queue <int> Q;
    Q.push(s);
    vis[s] = 1;
    dis[s] = 1.0;
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        vis[u] = 0;
        for (int i = f[u]; i; i = e[i].u) {
            int v = e[i].v;
            if (dis[v] < dis[u] * e[i].w / 100) {
                dis[v] = dis[u] * e[i].w / 100;
                if (!vis[v]) {
                    Q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
}
int main() {
    int t, n, m, u, v, w;
    scanf("%d", &t);
    while (t--) {
        cnt = 0;
        memset(f, 0, sizeof(f));
        memset(dis, 0, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        scanf("%d%d", &n, &m);
        for (int i = 0; i < m; i++) {
            scanf("%d%d%d", &u, &v, &w);
            Add(u, v, w);
            Add(v, u, w);
        }
        Spfa(1);
        printf("%.6f\n", dis[n] * 100);
    }
    return 0;
}