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;}