🔍 解题思路详解：最大概率路径问题

1. 问题分析

我们需要找到从起点（节点1）到终点（节点n）的路径，使得该路径的总成功概率最大。每条街道有一个通过概率p%，路径的总概率是各街道概率的乘积。

2. 关键观察

• 概率乘积特性：路径概率是各边概率的乘积，不是求和
• 转化为最优化问题：求乘积最大路径 ≡ 求对数求和最大路径（但本题直接处理乘积更直观）
• 无环限制：最优路径不会包含环路，因为环路只会降低总概率

3. 算法选择

使用优先队列优化的Dijkstra算法的变种：

• 传统Dijkstra找最小路径和
• 本题需要找最大路径积
• 因此需要：
  • 使用最大堆（优先队列从大到小排序）
  • 松弛条件改为取更大的概率积

4. 具体步骤

graph TD
    A[初始化: prob[1]=1.0, 其他=0.0] --> B[优先队列加入起点(1.0,1)]
    B --> C{队列非空?}
    C -->|是| D[取出当前最大概率节点u]
    D --> E{是终点n?}
    E -->|是| F[返回结果]
    E -->|否| G[遍历u的邻居v]
    G --> H[计算新概率 new_prob = prob[u]*p/100]
    H --> I{new_prob > prob[v]?}
    I -->|是| J[更新prob[v], 入队]
    I -->|否| C
    J --> C
    C -->|否| K[输出结果]

5. 数学处理技巧

• 避免浮点精度问题：
  • 使用double类型存储概率
  • 输出时固定6位小数
• 概率计算：
  • 初始化起点概率为1.0（100%）
  • 每次松弛操作：prob[v] = max(prob[v], prob[u]*p/100)

6. 复杂度分析

7. 边界情况处理

• 单一路径：如n=2时直接输出唯一街道概率
• 等概率路径：任选一条即可
• 高概率环路：算法自动避免（因为环路会降低概率）

8. 为什么不用DFS/BFS

• DFS会遍历所有路径，效率低（O(V!)）
• BFS不适合加权图
• Dijkstra的贪心性质能保证最优性

处理过程：

1. 初始化：prob[1]=1.0, prob[2]=prob[3]=0.0
2. 处理节点1：
   • 更新节点2：prob[2]=1.0*0.5=0.5
   • 更新节点3：prob[3]=1.0*0.3=0.3
3. 处理节点2：
   • 更新节点3：prob[3]=max(0.3, 0.5*0.5)=0.25
4. 最终结果：prob[3]=0.3 → 30%

9. 优化技巧

• 提前终止：当取出终点时立即返回
• 邻接表存储：节省空间
• 双向街道处理：建图时添加双向边

标程

#include <iostream>
#include <vector>
#include <queue>
#include <iomanip>
#include <cmath>

using namespace std;

typedef pair<double, int> pdi; // (probability, node)

struct Edge {
    int first;
    int second;
    Edge(int f, int s) : first(f), second(s) {}
};

void solve(int n, vector<vector<pair<int, int> > > &graph) {
    vector<double> prob(n+1, 0.0);
    priority_queue<pdi> pq;
    
    prob[1] = 1.0;
    pq.push(make_pair(1.0, 1));
    
    while (!pq.empty()) {
        double current_prob = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        
        if (u == n) break; // 到达终点
        if (current_prob < prob[u]) continue; // 已有更优路径
        
        for (size_t i = 0; i < graph[u].size(); ++i) {
            int v = graph[u][i].first;
            int p = graph[u][i].second;
            double new_prob = current_prob * p / 100.0;
            
            if (new_prob > prob[v]) {
                prob[v] = new_prob;
                pq.push(make_pair(new_prob, v));
            }
        }
    }
    
    cout << fixed << setprecision(6) << prob[n] * 100 << " percent" << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m;
    while (cin >> n && n != 0) {
        cin >> m;
        vector<vector<pair<int, int> > > graph(n+1);
        
        for (int i = 0; i < m; ++i) {
            int a, b, p;
            cin >> a >> b >> p;
            graph[a].push_back(make_pair(b, p));
            graph[b].push_back(make_pair(a, p)); // 双向街道
        }
        
        solve(n, graph);
    }
    
    return 0;
}