ACM-ICPC 2012 国内予選 Problem D 鉄道乗り継ぎ

鉄道乗り継ぎ

各会社ごとに全点対間最短路を求め、運賃を計算する。この運賃を使って、出発地から目的地の最安運賃を求める。

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

int main()
{
    const int INF = 99999999;

    while ( true )
    {
        int n, m, c, s, g;  cin>>n>>m>>c>>s>>g;
        if ( n==0 )
            break;
        s--; g--;

        //  D[c][x][y]: c社の路線でxからyに行くときの最短距離
        vector<vector<vector<int> > > D(c,vector<vector<int> >(n,vector<int>(n,INF)));
        for ( int i=0; i<m; i++ )
        {
            int x, y, d, c;  cin>>x>>y>>d>>c;
            x--; y--; c--; 
            D[c][x][y] = min(D[c][x][y],d);
            D[c][y][x] = min(D[c][y][x],d);
        }

        for ( int i=0; i<c; i++ )
            for ( int j=0; j<n; j++ )
            for ( int k=0; k<n; k++ )
            for ( int l=0; l<n; l++ )
                D[i][k][l] = min( D[i][k][l], D[i][k][j]+D[i][j][l] );

        //  F[x][y]: xからyに行くときの運賃
        vector<vector<int> > F(n,vector<int>(n,INF));
        vector<int> p(c);
        for ( int i=0; i<c; i++ )
            cin >> p[i];
        for ( int i=0; i<c; i++ )
        {
            vector<int> q(p[i]);
            for ( int j=1; j<p[i]; j++ )
                cin >> q[j];
            q.push_back(INF);
            vector<int> r(p[i]);
            for ( int j=0; j<p[i]; j++ )
                cin >> r[j];

            for ( int x=0; x<n; x++ )
            for ( int y=0; y<n; y++ )
            if ( D[i][x][y]<INF )
            {
                int fare = 0;
                for ( int j=0; j<p[i]; j++ )
                    if ( D[i][x][y]>q[j] )
                        fare += r[j]*min(D[i][x][y]-q[j],q[j+1]-q[j]);
                F[x][y] = min( F[x][y], fare );
            }
        }
        
        for ( int i=0; i<n; i++ )
        for ( int j=0; j<n; j++ )
        for ( int k=0; k<n; k++ )
            F[j][k] = min( F[j][k], F[j][i]+F[i][k] );

        cout << ( F[s][g]<INF ? F[s][g] : -1 ) << endl;
    }
}