3597: [Scoi2014]方伯伯运椰子
Time Limit: 30 Sec Memory Limit: 64 MBSubmit: 388 Solved: 239
[ Submit][ Status][ Discuss]
Description
Input
第一行包含二个整数N,M
接下来M行代表M条边,表示这个交通网络
每行六个整数,表示Ui,Vi,Ai,Bi,Ci,Di
接下来一行包含一条边,表示连接起点的边
Output
一个浮点数,保留二位小数。表示答案,数据保证答案大于0
Sample Input
5 10
1 5 13 13 0 412
2 5 30 18 396 148
1 5 33 31 0 39
4 5 22 4 0 786
4 5 13 32 0 561
4 5 3 48 0 460
2 5 32 47 604 258
5 7 44 37 75 164
5 7 34 50 925 441
6 2 26 38 1000 22
1 5 13 13 0 412
2 5 30 18 396 148
1 5 33 31 0 39
4 5 22 4 0 786
4 5 13 32 0 561
4 5 3 48 0 460
2 5 32 47 604 258
5 7 44 37 75 164
5 7 34 50 925 441
6 2 26 38 1000 22
Sample Output
103.00
HINT
1<=N<=5000
0<=M<=3000
1<=Ui,Vi<=N+2
0<=Ai,Bi<=500
0<=Ci<=10000
0<=Di<=1000
Source
#include<iostream> #include<cstdio> #include<queue> #include<vector> #include<bitset> #include<algorithm> #include<cstring> #include<map> #include<stack> #include<set> #include<cmath> #include<ext/pb_ds/priority_queue.hpp> using namespace std; const int maxn = 5E3 + 50; typedef double DB; const DB INF = 1E14; struct E{ int to; DB w; E(){} E(int to,DB w): to(to),w(w){} }edgs[maxn*20]; int n,m,cnt,s; DB dis[maxn]; bool vis[maxn]; vector <int> v[maxn]; void Add(int x,int y,DB w) { v[x].push_back(cnt); edgs[cnt++] = E(y,w); } bool SPFA(int x) { for (int i = 0; i < v[x].size(); i++) { E e = edgs[v[x][i]]; if (dis[e.to] > dis[x] + e.w) { dis[e.to] = dis[x] + e.w; if (vis[e.to]) return 1; vis[e.to] = 1; bool flag = SPFA(e.to); if (flag) return 1; } } vis[x] = 0; return 0; } bool Judge(DB now) { for (int i = 0; i < cnt; i++) edgs[i].w += now; for (int i = 1; i <= n; i++) dis[i] = INF,vis[i] = 0; dis[s] = 0; vis[s] = 1; bool flag = SPFA(s); for (int i = 0; i < cnt; i++) edgs[i].w -= now; return flag; } int main() { #ifdef DMC freopen("DMC.txt","r",stdin); #endif cin >> n >> m; n += 2; s = n - 1; for (int i = 1; i <= m; i++) { int x,y,a,b,c,d; scanf("%d%d%d%d%d%d",&x,&y,&a,&b,&c,&d); Add(x,y,b + d); if (c) Add(y,x,a - d); } DB L = 0,R = 1E12; for (int I = 0; I < 50; I++) { DB mid = (L + R) / 2.00; if (Judge(mid)) L = mid; else R = mid; } printf("%.2lf",(L + R)/2.00); return 0; }