Dijkstra

（1）a [ i ] [ j ] 存转账率（。。转后所得率。。）

（2）dis [ i ] 也就是 a [ 起点 ] [ i ] 

（3）f [ i ] 判断是否已经拓展过

（4）前驱结点 k

 

 

PS：ans * a[x][y]=100

       即 ans=100 / a[x][y]

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;double a[2001][2001],dis[2001],minn;int f[2001],n,m,k,x,y;void read(){ int xx,yy,zz; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d",&xx,&yy); scanf("%lf",&a[xx][yy]); a[xx][yy]=(100-a[xx][yy])/100; a[yy][xx]=a[xx][yy]; } cin>>x>>y;}void dijkstra(int x){ for(int i=1;i<=n;i++) dis[i]=a[x][i]; dis[x]=1; f[x]=1; for(int i=1;i<=n-1;i++) { minn=0; for(int j=1;j<=n;j++) if(f[j]==0&&dis[j]>minn) { k=j; minn=dis[j]; } f[k]=1; if(k==y) break; for(int j=1;j<=n;j++) if(f[j]==0&&dis[k]*a[k][j]>dis[j]) dis[j]=dis[k]*a[k][j]; }}int main(){ read(); dijkstra(x); printf("%.8lf",100/dis[y]); return 0; }