Repairing a Road

Repairing a Road

时间: 1ms        内存:128M

描述:

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.

输入:

输出:

示例输入:

3 2
1 2 1.5 1.8
2 3 2.0 1.5
2 1
1 2 2.0 1.8
0 0

示例输出:

2.589
1.976

提示:

参考答案(内存最优[1436]):

#include<stdio.h>
#include<math.h>
#define INF 0x3fffffff
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
typedef struct
{
	int x,y;
	double v,a;
}Edge;
Edge edges[500];
int R,C;
double cost[101][101];
void init();
void input();
void floyd();
double repair(int,int,double,double);
double solve();
int main()
{
	while(scanf("%d%d",&C,&R),C||R)
	{
		init();
		input();
		floyd();
		printf("%.3lf\n",solve());
	}
	return 0;
}
void init()
{
	int i,j;
	for(i=1;i<=C;i++)
	for(j=1;j<=C;j++)
	cost[i][j]=i==j?0:INF;
}
void input()
{
	int i,x,y;
	double v,a;
	for(i=0;i<R;i++)
	{
		scanf("%d%d%lf%lf",&x,&y,&v,&a);
		edges[i]={x,y,v,a};
		cost[x][y]=cost[y][x]=v;
	}
}
void floyd()
{
	int i,j,k;
	for(k=1;k<=C;k++)
	for(i=1;i<=C;i++)
	for(j=1;j<=C;j++)
	cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j]);
}
double repair(int x,int y,double v,double a)
{
	double t,g=0,r;
	r=cost[1][x];
	if(a!=1) g=max(log(v*log(a))/log(a)-r,0);
	t=r+g;
	return v*pow(a,-t)+g;
}
double solve()
{
	int i;
	double ans=cost[1][C];
	for(i=0;i<R;i++)
		ans=min(ans,min(cost[1][edges[i].x]+repair(edges[i].x,edges[i].y,edges[i].v,edges[i].a)+cost[edges[i].y][C],cost[1][edges[i].y]+repair(edges[i].y,edges[i].x,edges[i].v,edges[i].a)+cost[edges[i].x][C]));
	return ans;
}

参考答案(时间最优[12]):

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
const int MAXN = 110;
const int 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];
int x[MAXE], y[MAXE];
double v[MAXE], a[MAXE];
int 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(scanf("%d%d", &n, &m) != EOF)
    {
        if(n == 0 && m == 0) break;
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= n; ++j) mat[i][j] = 1e5;
            mat[i][i] = 0;
        }
        for(int i = 0; i < m; ++i)
        {
            int aa, bb;
            double cc;
            scanf("%d%d%lf%lf", &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();
        printf("%.3f\n", solve());
    }
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注