编写题解 1078: Repairing a Road

解题思路:

注意事项:要用

#include<iomanip>

#include<cstring>

#include<cmath>

#include<algorithm>

c++文件头

参考代码:

#include<iostream>

#include<iomanip>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

const int MAXN=110,MAXE=1010;

const double EPS=1e-6;

inline int sgn(double x)

{

   if(fabs(x)<EPS)return 0;

       return x>0?1:-1;

}

double fpai(double t,double v,double a)

{

   return 1-log(a)*v*pow(a,-t);

}

inline void update_min(double &a,const double &b)

{

   if(a>b)

       a=b;

}

double mat[MAXN][MAXN],v[MAXE],a[MAXE];

int x[MAXE],y[MAXE],n,m;

void floyd()

{

   for(int k=1;k<=n;k++)

       for(int i=1;i<=n;i++)

           for(int j=1;j<=n;j++)

               update_min(mat[i][j],mat[i][k]+mat[k][j]);

}

double find_t(int i,int x,int y,double l,double r)

{

   double L=l,R=r;

   while(R-L>EPS)

   {

       double mid=(L+R)/2;

       if(fpai(mid,v[i],a[i])>0)

           R=mid;

       else

           L=mid;

   }

   if(sgn(fpai(L,v[i],a[i]))!= 0)

       return l;

   return L;

}

double solve()

{

   double t,ans=mat[1][n];

   for(int i=0;i<m;i++)

   {

       t=find_t(i,x[i],y[i],mat[1][x[i]],ans);

       update_min(ans,t+v[i]*pow(a[i],-t)+mat[y[i]][n]);

       t=find_t(i,y[i],x[i],mat[1][y[i]],ans);

       update_min(ans,t+v[i]*pow(a[i],-t)+mat[x[i]][n]);

   }

   return ans;

}

int main()

{

   while(cin>>n>>m)

   {

       if(n==0&&m==0)

           break;

       for(int i=1;i<=n;i++)

       {

           for(int j=1;j<=n;j++)

               mat[i][j]=1e+5;

           mat[i][i]=0;

       }

       for(int i=0;i<m;i++)

       {

           int aa,bb;

           double cc;

           cin>>aa>>bb>>cc>>a[i];

           x[i]=aa;

           y[i]=bb;

           v[i]=cc;

           update_min(mat[aa][bb],cc);

           update_min(mat[bb][aa],cc);

       }

       floyd();

       cout<<fixed<<setprecision(3)<<solve()<<endl;

   }

   return 0;

}