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; } }