zoj 1655 单源最短路改为比例+最长路-白红宇

zoj 1655 单源最短路改为比例+最长路

阅读量：6762 次

发布时间：2019-06-26

本文共 972 字，大约阅读时间需要 3 分钟。

http://acm.zju.edu.cn/onlinejudge/showProblem.do?

problemId=655

没有理解清题意就硬套模板。所以WA了好几次。

解析看我的还有一篇http://blog.csdn.net/u011026968/article/details/35579035

贴代码

#include 
     
      #include 
      
       #include 
       
        using namespace std;#define ll long long#define INF2 0x03F3F3F3F#define INF 1.0const int N=100+10;int path[N];bool vis[N];double cost[N][N],lowcost[N],h[N];double ans;int n,m;void Dij(){    int i,j,beg=0;    double mmin;    memset(vis,0,sizeof(vis));    vis[beg]=1;    for(i=0;i
        
         lowcost[j])            {                lowcost[j]=lowcost[pre]*cost[pre][j];                path[j]=pre;            }        for(j=0;j
         
          mmin)            {                mmin=lowcost[j];                pre=j;            }        vis[pre]=1;    }}void Init(){    ans=0.0;    for(int i=0;i<=n;i++)        for(int j=0;j<=n;j++)            cost[i][j]=-1,lowcost[i]=0;}void Addedge(){    int u,v;    double tmp;    h[0]=0;    for(int i=1;i