首页 > 代码库 > CSU 1806 Toll
CSU 1806 Toll
最短路，自适应$Simpson$积分。
看了别人的题解才知道有个东西叫自适应$Simpson$积分。
有这样一个积分公式：$\int_a^b {f(x)dx} \approx \frac{{b - a}}{6}\left[ {f(a) + 4f\left( {\frac{{a + b}}{2}} \right) + f(b)} \right]$。这个东西用于计算不方便直接积分的时候的近似积分。
由于直接套公式会与实际有很大偏差，有一个改进：
要求$[L,R]$的积分，先令$m = \frac{{L + R}}{2}$，根据上面的公式，求出$[L,R]$的公式值${s_0}$，以及$[L,m]$的公式值${s_1}$，$[m,R]$的公式值${s_2}$。
如果${s_0}$与${s_1} + {s_2}$很接近，那么可以认为$[L,R]$的积分就是${s_0}$；否则进行递归，分别求$[L,m]$的积分和$[m,R]$的积分。
知道了这个东西之后，这题就变成水题了......
#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-8;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x){ char c = getchar(); x = 0;while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - ‘0‘; c = getchar(); }}int n,m,T;struct Edge{int u,v,c,d,nx;}e[200];int h[20],sz;void add(int u,int v,int c,int d){ e[sz].u=u; e[sz].v=v; e[sz].c=c; e[sz].d=d; e[sz].nx=h[u]; h[u]=sz++;}double SPFA(double x){ double dis[20]; bool flag[20]; for(int i=1;i<=n;i++) dis[i]=999999999999.0; memset(flag,0,sizeof flag); queue<int>Q; flag[1]=1; Q.push(1); dis[1]=0; while(!Q.empty()) { int top=Q.front(); Q.pop(); flag[top]=0; for(int i=h[top];i!=-1;i=e[i].nx) { if(dis[top]+e[i].c*x+e[i].d<dis[e[i].v]) { dis[e[i].v]=dis[top]+e[i].c*x+e[i].d; if(flag[e[i].v]==0) { flag[e[i].v]=1; Q.push(e[i].v); } } } } return dis[n];}double get(double L,double R){ return (R-L)*(SPFA(L)+4*SPFA((L+R)/2)+SPFA(R))/6;}double Ans(double L,double R){ double m=(L+R)/2; double s0,s1,s2; s0=get(L,R); s1=get(L,m); s2=get(m,R); if(fabs(s0-(s1+s2))<=eps) return s0; else return Ans(L,m)+Ans(m,R);}int main(){ while(~scanf("%d%d%d",&n,&m,&T)) { memset(h,-1,sizeof h); sz=0; for(int i=1;i<=m;i++) { int u,v,c,d; scanf("%d%d%d%d",&u,&v,&c,&d); add(u,v,c,d); } printf("%.8lf\n",Ans(0,1.0*T)/T); } return 0;}
CSU 1806 Toll
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。