AOJ1182 鉄道乗り継ぎ

解法

---

ワーシャった(小並感)
最初はワーシャって会社別に各駅までの最短距離を求める。
その次は、与えられたグラフを20000くらい(距離≦200 * 駅数≦100 より)までシュミレートして愚直に運賃を求める。
で、それを最初のグラフと照らし合わせながら、最短距離を運賃に変えたグラフにする。ついでに会社もまとめる。
最後にもう一回ワーシャって最安運賃を求める。

ソース

---

#include<iostream>
#include<queue>
#include<map>
 
using namespace std;
 
typedef pair < int , int > Pi;
const int INFTY = ( 1 << 28 );
 
int main(){
  int n, m, c, s, g;
  int station[21][101][101];
  int COST[21][20001];
 
  while(cin >> n >> m >> c >> s >> g, n){
    fill_n(**station, 21*101*101, INFTY);
    fill_n(*COST, 21 * 20001, 0);
    for(int i = 0 ; i < 21 ; i++ ){
      for(int j = 0 ; j < 101 ; j++ ) station[i][j][j] = 0;
    }
    for(int i = 0 ; i < m ; i++ ){
      int x, y, d, c;
      cin >> x >> y >> d >> c;
      station[c][x][y] = station[c][y][x] = min( station[c][x][y], d);
    }
 
    //わーしゃる
    for(int i = 1 ; i <= c ; i++ ){
      for(int j = 1 ; j <= n ; j++ ){
        for(int k = 1 ; k <= n ; k++ ){
          for(int l = 1 ; l <= n ; l++ ){
            station[i][k][l] = min( station[i][k][l], station[i][k][j] + station[i][j][l]);
          }
        }
      }
    }
    int p[21];
    for(int i = 1 ; i <= c ; i++ ){
      cin >> p[i];
    }
    int cost[52], dist[52];
    for(int i = 1 ; i <= c ; i++ ){
      fill_n( dist, 52, 0);
      fill_n( cost, 52, 0);
      for(int j = 1 ; j < p[i] ; j++ ){
        cin >> dist[j];
      }
      for(int j = 1 ; j <= p[i] ; j++ ){
        cin >> cost[j];
      }
      int diff = cost[1];
      int pos = 1;
      for(int j = 1 ; j < 20001 ; j++ ){
        if( pos < p[i] && dist[pos] < j) pos++;
        COST[i][j]= COST[i][j-1] + cost[pos];
      }
    }
    int ret[101][101];
    fill_n( *ret, 101 * 101, INFTY);
    for(int i = 1 ; i <= c ; i++ ){
      for(int j = 1 ; j <= n ; j++ ){
        for(int k = 1 ; k <= n ; k++ ){
          if(station[i][j][k] != INFTY) ret[j][k] = min( ret[j][k], COST[i][station[i][j][k]]);
        }
      }
    }
    for(int i = 1 ; i <= n ; i++ ){
      for(int j = 1 ; j <= n ; j++ ){
        for(int k = 1 ; k <= n ; k++ ){
          ret[j][k] = min( ret[j][k], ret[j][i] + ret[i][k]);
        }
      }
    }
 
    if(ret[s][g] == INFTY) cout << -1 << endl;
    else cout << ret[s][g] << endl;
  }
    return(0);
 
}