#include<bits/stdc++.h> using namespace std; int n,m,x,y,z,a,b,vis[2001]; double dis[2001],g[2001][2001]; int main() { cin>>n>>m; for(int i=1;i<=m;i++){ cin>>x>>y>>z; g[y][x]=g[x][y]=1-z*0.01; } cin>>a>>b; for(int i=1;i<=n;i++){ dis[i]=g[a][i]; } dis[a]=1; vis[a]=1; for(int i=1;i<n;i++){ double temp=-1; int t=-1; for(int j=1;j<=n;j++){ if(vis[j]==0&&temp<dis[j]){ temp=dis[j]; t=j; } } vis[t]=1; for(int j=1;j<=n;j++){ if(vis[j]==0){ dis[j]=max(dis[j],dis[t]*g[t][j]); } } } double ans=100/dis[b]; printf("%.8lf",ans); return 0; }

这题不难，修改一本通1381AC代码即可。 #include<bits/stdc++.h> using namespace std; double n,m,a[2001],b[2001][2001],s[2001],x,y; int c,d,e=1,z,f,g; int no(int f){ for(int i=1;i<=e;i++){ if(s[i]f){ return 0; } } return 1; } int main(){ cin>>n>>m; for(int i=0;i<=n;i++){ for(int j=0;j<=n;j++){ b[i][j]=-1; } } for(int i=1;i<=m;i++){ cin>>c>>d; if(b[c][d]-1&&b[d][c]-1){ cin>>x; b[c][d]=1-x/100; } else{ cin>>x; b[c][d]=max(b[c][d],1-x/100); } b[d][c]=b[c][d]; } cin>>f>>g; s[1]=f; for(int i=1;i<=n;i++){ a[i]=b[1][i]; } while(e<n){ y=-1; for(int i=1;i<=n;i++){ if(a[i]>y&&no(i)&&a[i]!=-1){ z=i; y=a[i]; } } e++; s[e]=z; for(int i=1;i<=n;i++){ if(b[z][i]!=-1&&no(i)){ if(a[i]-1){ a[i]=a[z]*-b[z][i]; } else{ a[i]=max(a[i],a[z]*b[z][i]); } } } } cout<<setprecision(8)<<fixed<<abs(100/a[g]); return 0; }

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
struct node {int v;double w;
    bool operator<(node fa)const {
        return w < fa.w;
    }
}x;double dis[100005];int n, m, vis[100005];
vector <node> mp[100005];void dijk(int s) {
    priority_queue <node> q;
	x.v=s;x.w=1;q.push(x);dis[s] = 1;
    while (!q.empty()) {node p = q.top();q.pop();
        if (vis[p.v] == 1) { continue; }vis[p.v] = 1;
        for (int i = 0;i < mp[p.v].size();i++) {
            node tmp = mp[p.v][i];
            if (dis[tmp.v] < dis[p.v] * tmp.w) {
                dis[tmp.v] = dis[p.v] * tmp.w;
                x.v=tmp.v;x.w=dis[tmp.v];
                q.push(x);
            }
        }
    }
}int main() {cin >> n >> m;
    for (int i = 1;i <= m;i++) {
        int u, v, w;cin >> u >> v >> w;
        mp[u].push_back({ v, 1 - w / 100.0 });
        mp[v].push_back({ u, 1 - w / 100.0 });
    }int a, b;cin >> a >> b;dijk(a);
    printf("%.8f", 100.0 / dis[b]);
}