Repairing a Road（floyd算法）
You live in a small town with R bidirectional roads connecting C crossings and you want to go from crossing 1 to crossing C as soon as possible. You can visit other crossings before arriving at crossing C, but it’s not mandatory.You have exactly one chance to ask your friend to repair exactly one existing road, from the time you leave crossing 1. If he repairs the i-th road for t units of time, the crossing time after that would be viai-t. It’s not difficult to see that it takes vi units of time to cross that road if your friend doesn’t repair it.
You cannot start to cross the road when your friend is repairing it.
Input
There will be at most 25 test cases. Each test case begins with two integers C and R (2<=C<=100, 1<=R<=500). Each of the next R lines contains two integers xi, yi (1<=xi, yi<=C) and two positive floating-point numbers vi and ai (1<=vi<=20,1<=ai<=5), indicating that there is a bidirectional road connecting crossing xi and yi, with parameters vi and ai (see above). Each pair of crossings can be connected by at most one road. The input is terminated by a test case with C=R=0, you should not process it.
Output
For each test case, print the smallest time it takes to reach crossing C from crossing 1, rounded to 3 digits after decimal point. It’s always possible to reach crossing C from crossing 1.
Sample Input
3 2
1 2 1.5 1.8
2 3 2.0 1.5
2 1
1 2 2.0 1.8
0 0
Sample Output
2.589
1.976
题意：给C个顶点(2<=C<=100), R(1<=R<=500)条边, 的无向图. 其中每条边上有起点, 终点, 时间权值vi, 和另一参数ai。如果这道路总共修了t时间，那么这条路的花费就会变成 vi * ai ^ (-t)。求从1到C的最小时间
之前课程设计的时候写了这题，当时对最短路算法没有现在的深刻了解，看这道题的时候比较懵，看了别人写的题解，然后觉得清晰了不少，自己写写，整理整理思路。。
分析：这题要求最小时间，那么是最短路问题。 然后求的是1到C的距离，C的范围不大，采用floyd算法，时间复杂度约为O(C^3).基本就是floyd算法的时间。
题中修一条路如果用了t时间，这条路的话费就会变成vi*ai^(-t)， 单调递减函数，可以从这里看到当a!=1时，t越大，所用时间越少，但既然是求最少时间，为什么修的越久越好？ 噗，这个就是题意部分的了， 路可以任意时候开始修，但是修路期间不能通过这条路。
那么这时候求出修路的最长时间+经过某条路的时间+到达C点的最短时间，取最小即为所求
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
#define mem(a,n) memset(a,n,sizeof(a))
const double INF=0x3f3f3f3f+1.0;
const double eps=1e-6;
typedef long long LL;
const int N=105;
double d;
int C,R;
struct Edge
{
int u,to;
double v,a;
};
queue<Edge>que;
求两点间最短距离
void floyd()
{
for(int k=1; k<=C; k++)
for(int i=1; i<=C; i++)
for(int j=1; j<=C; j++)
{
if(d>d+d)
d=d+d;
}
}
double solve(double sum)
{
Edge tou;
while(!que.empty())
{
tou=que.front();
que.pop();
double t=0;
if(abs(tou.a-1)>eps) ///若a不为1时，a为1时会发生除0错误
{ ///根据y =t+v*a^(-t) => y'=1+(-v*a^(-t)ln(a))=0
/// => a^t=v*ln(a) => t=log(a,v*ln(a))
/// => t=ln(v*ln(a))/ln(a)
t=log(tou.v*log(tou.a))/log(tou.a);
}
t=max(t,d);///求修 1->tou.u 这条路的最长时间
sum=min(sum,t+tou.v*pow(tou.a,-t)+d);///sum为总的最短时间
}
return sum;
}
int main()
{
while(~scanf("%d%d",&C,&R)&&C&&R)
{
while(!que.empty())///清空队列
que.pop();
///初始化最短时间
for(int i=1; i<=C; i++)
for(int j=1; j<=C; j++)
{
if(i==j) d=0;
else d=INF;
}
Edge E;
for(int i=0; i<R; i++)
{
scanf("%d%d%lf%lf",&E.u,&E.to,&E.v,&E.a);
int t1=E.u,t2=E.to;
d=E.v;
d=E.v;
que.push(E);
int tmp=E.u;
E.u=E.to;
E.to=tmp;
que.push(E);
}
floyd();
double ans=d;
printf("%.3lf\n",solve(ans));
}
return 0;
}
文档来源：51CTO技术博客https://blog.51cto.com/u_13696685/2989971
页:
[1]