http://poj.org/problem?id=2472
spfa

题意很简单，求概率乘积最大路

边权和距离数组都用double，然后存边权的时候直接存w/100.0

初始化的时候将所有距离初始化为0，并把dist[1]初始化成1(算乘积，所以必须得从1开始乘过去)

然后松弛操作更新成乘积更大的结果

#include <iostream>
#include<cmath>
#include<vector>
#include<algorithm>
#include<queue>
#include<utility>
#include<cstdlib>
#include<cstring>
#include<iomanip>
using namespace std;
const int N = 1e3 + 10, INF = 0x3f3f3f3f, MOD = 9987;
int n, m;
bool vis[N];
double dist[N];
struct Edge{
  int v;
  double w;
};
vector<Edge> adj[N];
void spfa()
{
  memset(vis, 0, sizeof vis);
  for (int i = 1; i <= n; i++)
    dist[i] = 0;
  dist[1] = 1;
  queue<int> q;
  q.push(1), vis[1] = true;
  while (!q.empty())
  {
    int u = q.front();
    q.pop(), vis[u] = false;
    for (int i = 0; i < adj[u].size(); i++)
    {
      int v = adj[u][i].v;
      double w = adj[u][i].w;
      if (dist[v] < dist[u] * w)
      {
        dist[v] = dist[u] * w;
        if (!vis[v])
          q.push(v), vis[v] = true;
      }
    }
  }
}
int main() 
{
  cin.tie(0)->sync_with_stdio(false);
  while (cin >> n)
  {
    if (n == 0)
      break;
    cin >> m;
    for (int i = 1; i <= n; i++)
      adj[i].clear();
    for (int i = 1, u, v, w; i <= m; i++)
    {
      cin >> u >> v >> w;
      adj[u].push_back({v, w / 100.0});
      adj[v].push_back({u, w / 100.0});
    }
    spfa();
    cout << fixed << setprecision(6) << dist[n] * 100 << " percent" << '\n';
  }

  return 0;
}