Repairing a Road （C++代码）

解题思路:





注意事项:
累死宝宝了，夜晚最后一个程序




参考代码:

#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) {
    //t - v * pow(a, -t)
    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;
        //cout<<fpai(mid, v[i], a[i])<<endl;
        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());
    }
}