Problem 2. drive Input file: drive.in Output file: drive.out Time limit: 2 second 工头cky 最近开了一家贸易公司，开始经商。作为cky 的忠实小弟，jyb 当了cky 老总的司机。一天晚上， cky 突然找到了一个新的客户，所以第二天一早要急着从成都去上海谈生意（设全国一共有n 个城市, 成都 编号为1，上海编号为n），城市之间有高速公路，每条高速公路都有一个最高限速和长度。cky 想：我应该 在今晚就告诉客户我最快多久能到上海，不然客户就可能先和别人谈生意了。所以他就让jyb 计算一下最快 多久能到。 jyb 作为一名经验丰富的老司机，看了一眼天气预报，天气预报说：全国范围内有一条高速公路第二天可能 下大雨（大雨天气的话，车速会下降75%），但坑爹的是居然不知道是哪一条，准确信息要第二天一早才知 道。现在jyb 拥有全国高速公路图，为了回答一个尽量早但又不失信于客户的时间，jyb 想请你帮帮忙。 ps: 虽然cky 很急，但是他还是告诫jyb 不能超速行驶。 第二天知道哪会下雨后，jyb 自然会作出正确的抉择。 迟到肯定就是失信于客户啦！ Input 第1 行，2 个整数n;m，表示城市数和高速公路数。 接下来m 行，每行4 个整数u; v; speed; length，表示该条高速公路连接的两个城市u; v，以及最高限速speed 和路长length。 Output 输出满足题意的时间，保留4 位小数。 Sample drive.in drive.out 3 3 1 2 100 100 2 3 100 100 1 3 100 400 4.0000 drive.in drive.out 2 1 1 2 100 100 4.0000 Note • 对于30% 的数据，1 n 102,1 m 103; • 对于100% 的数据，1 n 4 103,1 m 104,60 speed 120 ,200 length 1000。
Drive：最短路 如果没有大雾天气，很显然就是求一个最短路就行了。但是由于大雾天气的存在，如果大雾天气出现在乐最短路的路径上，那么肯定不能按照最快的时间到达，如果这样的话很可能就失信与客户。所以我们就需要枚举最短路径上每条高速公路出现大雾天气的情况，再求最短路，可得一个最糟的情况，即得到在不失信于客户的前提下的最快时间。 注意到数据范围，每条高速公路的行驶时间最多相差10倍，spfa的时间复杂度的上界大概为O(kM)，k = 10，而朴素Dijkstra求一次最短路为稳定O(n^2)，总的最坏为O(n^3)，所以我们采用spfa或者堆优化Dijkstra算法 (jyb写的STL堆优被卡了两个点)求最短路。
#include <cstdio> #include <cmath> #include <cstring> #include <string> #include <cstdlib> #include <algorithm> #include <iostream> using namespace std; const int maxn = 4010; const int maxm = 20010; struct edge { int u,v,next; double w; }e[maxm]; int h[maxn],num; double dis[maxn]; int pre[maxn]; bool vis[maxn]; int q[maxn],head,tail; int n,m; inline void build(int u, int v, double w) { num++; e[num].u = u, e[num].v = v, e[num].w = w, e[num].next = h[u], h[u] = num; } inline void init() { for(int i = 2; i <= n; i++) dis[i] = 1000000.0; head = 0; tail = 1; q[0] = 1; vis[1] = true; } double spfa(bool first) { int v,u; init(); while(head != tail) { u = q[head]; for(int i = h[u]; i; i = e[i].next) { v = e[i].v; if(dis[v] > dis[u]+e[i].w) { dis[v] = dis[u]+e[i].w; if(first) pre[v] = i; if(!vis[v]) { vis[v] = true; q[tail] = v; tail = (tail+1)%n; } } } vis[u] = false; head = (head+1)%n; } return dis[n]; } int main() { freopen("drive.in","r",stdin); freopen("drive.out","w",stdout); scanf("%d%d",&n,&m); int u,v; double sp,len; for(int i = 1; i <= m; i++) scanf("%d%d%lf%lf",&u,&v,&sp,&len), build(u,v,len/sp); int now = n; double ans = spfa(true); while(now != 1) { e[pre[now]].w *= 4.0; ans = max(ans,spfa(false)); e[pre[now]].w /= 4.0; now = e[pre[now]].u; } printf("%.4lf\n",ans); return 0; }