Repairing a Road （C语言代码）Floyd算法

参考代码:

#include <stdio.h>
#include <math.h>
#include <string.h>

#define INF 1e9
#define eps 1e-6

 typedef struct EDGE
 {
     int from,to;
     double v,a;
 }edge;
edge que [1000];//用来存储输入的边,便后之后的逐条逐条边的分析
int head,rear;
double cost[110][110];//用于存储两点间的最短路（Floyd算法）
int C,R;//C,R分别是顶点和边的数目
double sum;//存储结果




 void floyd()//Floyd算法
{
    int k,i,j;
    for (k=1;k<=C;k++)
      for (i=1;i<=C;i++)
         for (j=1;j<=C;j++)
            if(cost[i][k]+cost[k][j]<cost[i][j])
                cost[i][j]=cost[i][k]+cost[k][j];

}


 void calc()
 {

     /** 记从第1号点到某边的起点from的最短时间为t0（已知）；
        记从该边的终点to到第C号点的最短时间为t2（已知）；
        记修完该条边的时间为t，则修完后走完这条边的时间为v/(a^t)；
        则从第1号点到第C号点的路径（包含这条边）的时间y的函数为
        y=max{t0,t}+v/(a^t)+t2;
        现题意是求y(t)的最小值
        1）若t<=t0;则y=t0+v/(a^t)+t2; y随t的增大而减小，而t<=t0，故t取t0时，y得最小值；
        2）若t>t0;则y=t+v/(a^t)+t2; 用求导法求最小值，y'=1+(-v*a^(-t)ln(a))=0 可得t取ln(v*ln(a))/ln(a)时，y取最小值；
            记tmp=ln(v*ln(a))/ln(a)

        综上故有，若t0<tmp，则当t=tmp时，y取最小值；若t0>=tmp;则在t=t0处取最小值。（可画图理解）
     **/
     int from,to;
     double v,a;

     while (head!=rear)
     {
         from=que[head].from;//出队一条边
         to=que[head].to;
         v=que[head].v;
         a=que[head].a;
         head++;

         double t0=cost[1][from];
         double tmp;
         if(fabs(a-1)>eps)  tmp=log(v*log(a))/log(a);//防止a=1时产生除0错
         else tmp=t0;
         double t2=cost[to][C];


         if (tmp<t0)
         {
             if (t0+v/pow(a,t0)+t2<sum)
                 sum=t0+v/pow(a,t0)+t2;
         }
         else
         {
              if (tmp+v/pow(a,tmp)+t2<sum)
                  sum=tmp+v/pow(a,tmp)+t2;
        }

    }

}

int main()
{
    while (scanf("%d %d",&C,&R)==2&&C&&R)
    {
        head=rear=0;//设置队列
        int i,j;
        for (i=1;i<=C;i++)//初始化cost数组
            for(j=1;j<=C;j++)
                    if (i==j)
                        cost[i][j]=0;
                    else
                        cost[i][j]=INF;


        int from,to; double v,a;//输入边及其参数
        for(i=0;i<R;i++)
        {
            scanf("%d %d %lf %lf",&from,&to,&v,&a);
            if(cost[from][to]>v)
                    cost[from][to]=cost[to][from]=v;//无向图，不考虑修路，则一条路的时间花费为v

            que[rear].from=from;//把无向边入队，两个方向各存储一次，方便接下去对经过Floyd算法处理过的cost数组进行修路处理时，会用到不同方向的边
            que[rear].to=to;
            que[rear].v=v;
            que[rear].a=a;
            rear++;
            que[rear].from=to;
            que[rear].to=from;
            que[rear].v=v;
            que[rear].a=a;
            rear++;
        }
        floyd();//基本上所有数据结构均为全局变量，直接调用Floyd算法处理；
        sum=cost[1][C];
        calc();
        printf("%.3lf\n",sum);
    }
    return 0;
}