Problem 3: Milk Routing

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<algorithm>

#define MN 1005
#define INF 1000007
#define pb push_back
#define mp make_pair
#define fr first
#define se second

const double eps = 1e-12;

using namespace std;

int N, M, X, I, J, L, C, ans = INF*1000, c, u[INF];
vector< pair< int, pair<int, int> > >g[MN];
vector< pair<int, int> >v[MN];
void Init(){
    cin>>N>>M>>X;
    for(int i=1; i<=M; i++){
        cin>>I>>J>>L>>C;
        if(I<J){
            swap(I, J);
        }
        if(I != J){
            g[I].pb( mp( J, mp(L, C) ) );
        }
    }
}
void solve(){
    if(N == 1){
        cout<<0<<endl;
        return;
    }
    int i, j, k;
    v[1].pb( mp(0, INF) );
    for(i=2; i<=N; i++){
        for(j=0; j<g[i].size(); j++){
            J = g[i][j].fr;
            L = g[i][j].se.fr;
            C = g[i][j].se.se;
            for(k=0; k<v[J].size(); k++){
                c = min(C, v[J][k].se);
                if(u[c] == 0){
                    v[i].pb( mp( L+v[J][k].fr, c ) );
                    u[c] = v[i].size();
                }
                else {
                    v[i][ u[c]-1 ].fr = min(v[i][ u[c]-1 ].fr, L+v[J][k].fr);
                }
            }
        }
        for(j=0; j<v[i].size(); j++){

            u[ v[i][j].se ] = 0;
        }
    }
    for(i=0; i<v[N].size(); i++){
        ans = min(ans, v[N][i].fr + X/v[N][i].se);
    }
    cout<<ans<<endl;
}
main(){
    freopen("mroute.in", "r", stdin);   freopen("mroute.out", "w", stdout);
    Init();
    solve();
    return 0;
}