URAL 1980 Road to Investor（二分+最短路）

n个点m条边的无向图，每条路有固定的长度，然后有一个速度上限。要求在T时间内能从1到达n，最少超速多少？

显然是二分答案然后求最短路。不过当二分枚举的超速很大而某条边的距离很小的时候，经过这条边的时间是会很小很小的，所以要将所有的时间单位扩大1e9倍，才不会丢失精度。。。

#include<algorithm>#include<iostream>#include<cstring>#include<fstream>#include<sstream>#include<cstdlib>#include<vector>#include<string>#include<cstdio>#include<bitset>#include<queue>#include<stack>#include<cmath>#include<map>#include<set>#define FF(i, a, b) for(int i=a; i<b; i++)#define FD(i, a, b) for(int i=a; i>=b; i--)#define REP(i, n) for(int i=0; i<n; i++)#define CLR(a, b) memset(a, b, sizeof(a))#define debug puts("**debug**")#define LL long long#define PB push_back#define MP make_pairusing namespace std;const double INF = 1e50;const int maxn = 10010;const double eps = 1e-7;struct Edge{    int from, to;    double dist;    Edge(){}    Edge(int a, int b, double c):from(a), to(b), dist(c){}};struct Heap{    double d;    int u;    Heap(){}    Heap(double d, int u):d(d), u(u){}    bool operator<(const Heap& rhs) const    {        return d > rhs.d;    }};map<int, int> mp;bool flag;struct Dijkstra{    int n, m;    vector<int> G[maxn];    vector<Edge> edges;    bool done[maxn];    double d[maxn];    int p[maxn];    void init(int n)    {        this->n = n;        REP(i, n+1) G[i].clear();        edges.clear();    }    void add(int a, int b, double c, int id)    {        Edge e1 = Edge(a, b, c), e2 = Edge(b, a, c);        edges.PB(e1), edges.PB(e2);        m = edges.size();        G[a].PB(m-2), G[b].PB(m-1);        if(!flag) mp[m-2] = mp[m-1] = id;    }    void dijkstra(int s)    {        priority_queue<Heap> q;        REP(i, n+1) d[i] = INF;        d[s] = 0; CLR(done, 0);        q.push(Heap(0, s));        while(!q.empty())        {            Heap x = q.top(); q.pop();            int u = x.u;            if(done[u]) continue;            done[u] = 1;            REP(i, G[u].size())            {                Edge e = edges[G[u][i]];                if(d[e.to] > d[u] + e.dist)                {                    d[e.to] = d[u] + e.dist;                    p[e.to] = G[u][i];                    q.push(Heap(d[e.to], e.to));                }            }        }    }    void getpath(int s, int t, vector<int>& path)    {        while(t != s)        {            path.PB(p[t]);            t = edges[p[t]].from;        }        reverse(path.begin(), path.end());    }}solver;int n, m;double T;struct E{    int u, v;    double s, l;}e[maxn];bool ok(double mid){    solver.init(n);    FF(i, 1, m+1) solver.add(e[i].u, e[i].v, e[i].l/(e[i].s+mid)*1000000000, i);    solver.dijkstra(1);    flag = 1;    return solver.d[n] <= T;}int main(){    while(~scanf("%d%d", &n, &m))    {        mp.clear();        flag = 0;        FF(i, 1, m+1) scanf("%d%d%lf%lf", &e[i].u, &e[i].v, &e[i].s, &e[i].l);        scanf("%lf", &T);        T *= 1000000000;        double L = 0, R = 1e8, M;        while(L + eps < R)        {            M = (L + R) / 2;            if(ok(M)) R = M;            else L = M;        }        printf("%.6lf ", L);        vector<int> path;        solver.getpath(1, n, path);        int nc = path.size();        printf("%d\n", nc);        REP(i, nc) printf("%d%c", mp[path[i]], i == nc-1 ? '\n' : ' ');    }    return 0;}