题目链接：http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1806

解法：被积函数，就是用spfa跑出来的结果，然后掏出辛普森就可以 了。注意加的边是单向边。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200;
const double eps = 1e-8;
struct edge{
    int v,next;
    double c,d;
}E[maxn];
int head[20], edgecnt;
int n, m;
void init(){
    memset(head,-1,sizeof(head));
    edgecnt=0;
}
void add(int u,int v,double c, double d){
    E[edgecnt].c=c,E[edgecnt].d=d,E[edgecnt].v=v,E[edgecnt].next=head[u],head[u]=edgecnt++;
}
double spfa(double x){
    double dis[20];
    bool vis[20];
    for(int i=1; i<=n; i++) dis[i]=999999999999.0, vis[i]=0;
    queue<int>q;
    q.push(1);
    dis[1]=0;
    while(!q.empty())
    {
        int u=q.front(); q.pop(); vis[u]=0;
        for(int i=head[u];i+1;i=E[i].next){
            int v=E[i].v;
            if(dis[v]-dis[u]-E[i].c*x-E[i].d>eps){
                dis[v]=dis[u]+E[i].c*x+E[i].d;
                if(!vis[v]){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    return dis[n];
}
double cal(double L, double R){
    return (R-L)*(spfa(L)+4.0*spfa((L+R)/2)+spfa(R))/6.0;
}
double Simpon(double L, double R){
    double mid=(L+R)/2.0;
    double s0,s1,s2;
    s0=cal(L,R);
    s1=cal(L,mid);
    s2=cal(mid,R);
    if(fabs(s0-(s1+s2))<=eps) return s0;
    else return Simpon(L,mid)+Simpon(mid,R);
}
int main()
{
    int T;
    while(~scanf("%d%d%d",&n,&m,&T)){
        init();
        for(int i=1; i<=m; i++){
            int a,b;
            double c,d;
            scanf("%d %d %lf %lf",&a,&b,&c,&d);
            add(a,b,c,d);
            //add(b,a,c,d);
        }
        double ans=Simpon(0,1.0*T)/(1.0*T);
        printf("%.8f\n", ans);
    }
    return 0;
}