CSU 1806 Toll（自适應Simpson公式+Dijkstra+priority_queue）

1806: Toll

​ Submit Page    Summary    5 Sec 128 Mb 302 91 SpecialJudge

Description

 In ICPCCamp, there are

n cities and

m unidirectional roads between cities. The

i-th road goes from the a

i-th city to the b

i-th city. For each pair of cities

u and

v, there is at most one road from

u to

v.

As traffic in ICPCCamp is becoming heavier, toll of the roads also varies. At time

t, one should pay (c

i⋅t+d

i) dollars to travel along the

i-th road.

Bobo living in the 1-st city would like to go to the n-th city. He wants to know the average money he must spend at least if he starts from city 1 at

t∈[0,T]. Note that since Bobo's car is super-fast, traveling on the roads costs him

no time.

Formally, if

f(t) is the minimum money he should pay from city 1 to city

n at time

t, Bobo would like to find

Input

The first line contains 3 integers n,m,T (2≤n≤10,1≤m≤n(n-1),1≤T≤10

4).

The i-th of the following m lines contains 4 integers a

i,b

i,c

i,d

i (1≤a

i,b

i≤n,a

i≠b

i,0≤c

i,d

i≤10

3).

It is guaranteed that Bobo is able to drive from city 1 to city n.

Output

 A floating number denotes the answer. It will be considered correct if its absolute or relative error does not exceed 10

-6.

Sample Input

3 3 2

1 2 1 0

2 3 1 0

1 3 1 1

3 3 2

1 2 1 0

2 3 1 0

1 3 0 5

Sample Output

1.75000000

2.00000000

Hint

Source

        最短路，但是費用随着時間而變化，問最小費用關于時間積分的平均數。

        對于求積分，很早的時候大概是大一第一個學期的時候，學Python時候LWW老師就曾經給我們講過一個叫Simpson公式以及自适應Simpson公式的東西。當時呢學着覺得也沒啥用，不就是算個積分嗎，用處不大……

        然後這題就是一個計算積分的題目，正好就用到了自适應Simpson公式。所謂Simpon公式，就是指對于函數f(x)在一個區間[l,r]上的積分，可以近似等于(r-l)*(f(l)+f(r)+f(mid)/6。所謂近似，就是指可以有誤差，很顯然這個誤差一般來說非常的大，是以我們要用自适應的方式。那麼什麼是自适應Simpson公式呢？其實就是說自己設定一個eps，運用二分的思想，當Simpson(l,mid)+Simpson(mid,r)與Simpson(l,r)的查大于eps的時候，自動判定為誤差過大，于是繼續把區間分細，對區間[l,mid]和[mid,r]使用自适應Simpson公式計算，然後傳回兩者之和。一直這樣遞歸下去就可以得到誤差為eps的結果。至于時間複雜度這個我真的不知道……有沒有哪位dalao能告訴我。具體見代碼：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#define eps 1e-8
#define N 100
using namespace std;

typedef pair<double,int> P;
struct Edge{int y,c,d;};
vector<Edge> g[N];
const int INF=1e9;
double d[N];
int m,n,T;

inline double dijkstra(double t)
{
    priority_queue<P,vector<P>,greater<P> > q;
    for(int i=1;i<=n;i++) d[i]=INF;
    d[1]=0; q.push(P(0,1));
    while (!q.empty())
    {
        int j=q.top().second;
        double w=q.top().first;
        q.pop(); if (w-d[j]>eps) continue;
        for(int k=0;k<g[j].size();k++)
        {
            int y=g[j][k].y;
            double dist=w+g[j][k].c*t+g[j][k].d;
            if (d[y]-dist>eps) {d[y]=dist; q.push(P(d[y],y));}
        }
    }
    return d[n];
}

double simpson(double l,double r)
{
    double mid=(l+r)/2.0;
    return (r-l)*(dijkstra(l)+dijkstra(r)+4*dijkstra(mid))/6.0;
}

double rsimpson(double l,double r)
{
    double mid=(l+r)/2.0;
    double A=simpson(l,r);
    double L=simpson(l,mid);
    double R=simpson(mid,r);
    if (fabs(A-L-R)>=eps) return rsimpson(l,mid)+rsimpson(mid,r);
                     else return A;
}

int main()
{
    while(~scanf("%d%d%d",&n,&m,&T))
    {
        memset(g,0,sizeof(g));
        for(int i=1;i<=m;i++)
        {
            int u,v,x,y;
            scanf("%d%d%d%d",&u,&v,&x,&y);
            g[u].push_back(Edge{v,x,y});
        }
        printf("%.7f\n",(double)rsimpson(0,T)/T);
    }
    return 0;
}