[CSU1806]Toll

题目：Toll

传送门：http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1806

题目简述：给定n个点m条有向边的有向图，每条边的花费是$b_i * t +d_i$,设f(t)表示给定t的时候1-n的最小花费,求：${\frac{\int_0^T{f(t)dt}}{T}}$

分析：

(1)f(t)可用最短路求出来。

(2)积分值可用自适应辛普森积分法计算。

注意：有向图！

代码：

#include <cstdio>

#include <cstring>

const int N=,QN=,M=;

const double EPS=1e-,INF=1e9;

int n,m;

int size,fi[N];

struct Edge{int to,next;double c,d;}e[M];

void Gadd(int x,int y,double c,double d){

    e[++size].to=y;e[size].c=c;e[size].d=d;e[size].next=fi[x];fi[x]=size;

}

int q[N+];double dis[N];bool use[N];

double F(double x){

    for(int i=;i<=n;++i)dis[i]=INF;

    int h=,t=;dis[q[t]=]=;

    for(int v;h!=t;){

        if((++h)==QN)h=;use[v=q[h]]=false;

        for(int i=fi[v],u;i;i=e[i].next){

            u=e[i].to;

            if(dis[v]+e[i].c*x+e[i].d<dis[u]){

                dis[u]=dis[v]+e[i].c*x+e[i].d;

                if(use[u])continue;

                if((++t)==QN)t=;use[q[t]=u]=true;

            }

        }

    }

    return dis[n];

}

double Simpson(double l,double r){

    return (r-l)*(F(l)+*F((l+r)/)+F(r))/;

}

double Abs(double x){return x<?-x:x;}

double Integral(double l,double r,double S){

    double mid=(l+r)/;

    double A=Simpson(l,mid);

    double B=Simpson(mid,r);

    if(Abs(A+B-S)<EPS)

        return S;else return Integral(l,mid,A)+Integral(mid,r,B);

}

int main(){

    for(double T,ans;~scanf("%d%d%lf",&n,&m,&T);){

        size=;memset(fi,,sizeof fi);

        for(int i=,a,b,c,d;i<=m;++i){

            scanf("%d%d%d%d",&a,&b,&c,&d);

            Gadd(a,b,(double)c,(double)d);

        }

        ans=Integral(,T,Simpson(,T))/T;

        printf("%.8f\n",ans);

    }

    return ;

}