luogu 1576
错误： 第31行 maxd 类型为double，赋成int！
解法： 把消耗转化为剩余 ， 运用最短路算法dijstra来找一遍最长路
#include<iostream> #include<cstring> #include<string> #include<algorithm> #include<queue> #include<vector> #include<cstdio> #include<cmath> using namespace std; double f[2001][2001],dis[2001]; bool vis[2001]; int n,m,s,t; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int x,y; double z; scanf("%d%d%lf",&x,&y,&z); f[x][y]=(100-z)/100.0; f[y][x]=f[x][y]; } scanf("%d%d",&s,&t); for(int i=1;i<=n;i++) dis[i]=f[s][i]; dis[s]=1,vis[s]=true; int kk=0; for(int k=1;k<=n-1;k++) { double maxd=0;// 不可为int ！这里错过！ for(int i=1;i<=n;i++) { if(dis[i]>maxd&&!vis[i]) maxd=dis[i],kk=i; } vis[kk]=true; if(kk==t) break; for(int i=1;i<=n;i++) { if(dis[kk]*f[kk][i]>dis[i]&&!vis[i]) dis[i]=dis[kk]*f[kk][i]; } } double ans; ans=100.0/dis[t]; printf("%.8lf",ans); return 0; }