分析：根據這個題學了一發自適應simpson積分（原來積分還可以這么求），然后就是套模板了

??????? 學習自適應simpson積分:http://blog.csdn.net/greatwall1995/article/details/8639135

#include <cstdio> #include <cstring> #include <queue> #include <cmath> #include <algorithm> using namespace std; typedef long long LL; const int N = 1e2 + 5; const double eps = 1e-9; const double INF = 1e12; int n,m,T,tot,head[15]; int a[N],b[N],c[N],d[N]; bool vis[15]; double dis[N]; struct Edge{int v,next;double w;Edge(int v=0,double w=0){this->v=v;this->w=w;}bool operator<(const Edge &rhs)const{return w>rhs.w;} }edge[N]; void add(int u,int v,double w){edge[tot].v=v;edge[tot].w=w;edge[tot].next=head[u];head[u]=tot++; } priority_queue<Edge>q; double F(double t){memset(head,-1,sizeof(head));tot=0;memset(vis,false,sizeof(vis));for(int i=1;i<=n;++i)dis[i]=INF;dis[1]=0;for(int i=0;i<m;++i){add(a[i],b[i],c[i]*t+d[i]);}q.push(Edge(1,dis[1]));while(!q.empty()){int u=q.top().v;q.pop();if(vis[u])continue;vis[u]=true;for(int i=head[u];~i;i=edge[i].next){int v=edge[i].v;if(!vis[v]&&dis[v]>dis[u]+edge[i].w){dis[v]=dis[u]+edge[i].w;q.push(Edge(v,dis[v]));}}}return dis[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 get(double a,double b,double eps){return asr(a,b,eps,simpson(a,b)); } int main(){while(~scanf("%d%d%d",&n,&m,&T)){for(int i=0;i<m;++i)scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);printf("%.6f\n",get(0,T,eps)/T);}return 0; } View Code

?

轉載于:https://www.cnblogs.com/shuguangzw/p/5842288.html

總結

以上是生活随笔為你收集整理的CSU 1806 Toll 自适应simpson积分+最短路的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。