ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 1182 Railway Connection

問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1182&lang=jp


・概要
路線図がグラフとして与えられます。
そのときの出発点から目的地までの最低運賃を求める問題です。
各鉄道会社によって運賃が変わり、さらに乗った距離によっても運賃は変わります。
制約等は省略。


・解法
ワーシャルフロイドを2回用いることで解くことができます。

まず入力で運賃が与えられたら、あらかじめすべての距離での運賃を計算指せておきます。駅の数は100以下、路線の距離は200以下なのでそれぞれ20000くらいまでの距離の運賃を計算しておけばよいです。

そして...
1回目のワーシャルフロイドで、それぞれの鉄道会社について各駅間の最短距離を求めます。
そのあとに各駅間の運賃をあらかじめ計算させておいた運賃リストをもとに求めます。
2回目のワーシャルフロイドで、すべての鉄道会社について各駅間の最低運賃を求めます。

これで求めたい値を求めることができました。

(※この問題は国内予選本番で解けなくて悔しい思いをした問題。 最初はダイクストラでいろいろやっていたがうまくいかなかった)


ソースコード

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;

#define REP(i,x,n) for(int i = x ; i < (int)(n) ; i++)
#define rep(i,n)  REP(i,0,n)
static const int INF = (1 << 29);

int n,m,c,s,g;
int p[55],q[55],r[55];
int tmpCost[20010][21],cost[101][101];
int dist[101][101][21];

int solve(){
   //wf
   for(int C = 1 ; C <= c ; C++){
      for(int k = 1 ; k <= n ; k++){
	 for(int i = 1 ; i <= n ; i++){
            for(int j = 1 ; j <= n ; j++){
	       dist[i][j][C] = min(dist[i][j][C], dist[i][k][C]+dist[k][j][C]);
            }
         }
      }
   }
	 
   rep(i,101)rep(j,101)cost[i][j] = (i==j) ? 0 : INF;
   
   for(int C = 1 ; C <= c ; C++){
      for(int i = 1 ; i <= n ; i++){
         for(int j = 1 ; j <= n ; j++){
	    if(dist[i][j][C]==INF)continue;
	    cost[i][j] = min(cost[i][j], tmpCost[dist[i][j][C]][C]);
         }
      }
   }
	 
   //wf
   for(int k = 1 ; k <= n ; k++){
      for(int i = 1 ; i <= n ; i++){ 
         for(int j = 1 ; j <= n ; j++){
	    cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j]);
         }
      }
   }
	 
   return (cost[s][g]==INF) ? -1 : cost[s][g];
}

void input(){
   memset(tmpCost,0,sizeof(tmpCost));
   rep(i,101)rep(j,101)rep(k,21)dist[i][j][k] = (i==j) ? 0 : INF;
	 
   for(int i = 0 ; i < m ; i++){
      int x,y,d,cc;
      scanf("%d%d%d%d",&x,&y,&d,&cc);
      dist[x][y][cc] = dist[y][x][cc] = min(d, dist[x][y][cc]);
   }
   
   for(int C = 1 ; C <= c ; C++)scanf("%d",&p[C]);

   for(int C = 1 ; C <= c ; C++){
      for(int i = 0 ; i < p[C] - 1 ; i++)scanf("%d",&q[i]);
      
      for(int i = 0 ; i < p[C] ; i++)scanf("%d",&r[i]);
      
      int T = 0;
      for(int i = 1 ; i <= 20000 ; i++){
	 if(T+1!=p[C] && i > q[T])T++;
	 tmpCost[i][C] = tmpCost[i-1][C] + r[T];
      }
   }
}

int main(){ 
   while(cin >> n >> m >> c >> s >> g){
      if((n|m|c|s|g)==0)break;
      input();
      cout << solve()<< endl;
   }
   return 0;
}