传送门:点击打开链接
题意:一个有向图,但是只有10个点。然后每条路的费用会随着时间变化,费用等于ci*t+di。可以认为车在路上行驶不花费时间,所以时间只与出发时间有关。
现在问从1到n去,在[0,T]这一段时间内出发,平均费用是多少。
思路:首先我们得能看出这个积分表达式才行,萌萌哒的叉姐已经提示我们了(业界良心啊。。
然后,Simpson求定积分,如果函数连续,且可以求出给定x时的y值,那么就能用了。
很显然,给定x值时,对于这个题,就相当于告诉你出发时间,后面显然就是个傻逼最短路。
所以这题只要看懂这个套路就是个傻逼题。。555555
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <bitset>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
#define fuck(x) cout<<"["<<x<<"]";
#define FIN freopen("input.txt","r",stdin);
#define FOUT freopen("output.txt","w+",stdout);
//#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
typedef pair<int, int>PII;const int MX = 1e3 + 5;
const int INF = 0x3f3f3f3f;struct Edge {int v, nxt, c, d;
} E[MX];
int Head[MX], erear;
void edge_init(int n) {erear = 0;for(int i = 1; i <= n; i++) Head[i] = -1;
}
void edge_add(int u, int v, int c, int d) {E[erear].v = v;E[erear].c = c;E[erear].d = d;E[erear].nxt = Head[u];Head[u] = erear++;
}int n, m, T;
double d[MX];double f(double x) {typedef pair<double, int> Data;priority_queue<Data, vector<Data>, greater<Data> > Q;for(int i = 1; i <= n; i++) d[i] = INF;d[1] = 0; Q.push(Data(0, 1));while(!Q.empty()) {Data ftp = Q.top(); Q.pop();if(ftp.first != d[ftp.second]) continue;int u = ftp.second;for(int i = Head[u]; ~i; i = E[i].nxt) {int v = E[i].v;double cost = x * E[i].c + E[i].d;if(d[u] + cost < d[v]) {d[v] = d[u] + cost;Q.push(Data(d[v], v));}}}return d[n];
}
double simpson(double a, double b) {double c = a + (b - a) / 2;return (f(a) + 4 * f(c) + f(b)) * (b - a) / 6;
}
double asr(double a, double b, double eps, double A) {double c = a + (b - a) / 2;double L = simpson(a, c), R = simpson(c, b);if(fabs(L + R - A) <= 15 * eps) return L + R + (L + R - A) / 15.0;return asr(a, c, eps / 2, L) + asr(c, b, eps / 2, R);
}
double asr(double a, double b, double eps) {return asr(a, b, eps, simpson(a, b));
}int main() {// FIN;while(~scanf("%d%d%d", &n, &m, &T)) {edge_init(n);for(int i = 1; i <= m; i++) {int u, v, c, d;scanf("%d%d%d%d", &u, &v, &c, &d);edge_add(u, v, c, d);}printf("%f\n", asr(0, T, 1e-6) / T);}return 0;
}