AOJ 0596 - Taxis

問題概要

町1から町NまでのN個の町があり、町と町の間には道路がある。道路はK本あり、すべての道路は異なる2つの町を結んでいる。N台のタクシーがあり、町iではi番目のタクシーに乗車でき、i番目のタクシーの運賃はC_iで連続して最大R_i区間しか移動できない。このとき町1から町Nへ行くための最小コストを求めよ。

制約

• 2 ≤ N ≤ 5000
• N - 1 ≤ K ≤ 10000
• 1 ≤ C_i ≤ 10000
• 1 ≤ R_i ≤ N

解法

dijkstra。
cost[どの町][残りR回乗車できる] := 最小コスト。
メモリ的にローカルで宣言すると多分やばい。

コード

#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX 5010
#define INF 1e9
#define F first
#define S second
typedef pair<int,int> pii;
typedef pair<pii,int> piii;
  
int N,K;
pii taxi[MAX];
vector<int> G[MAX];
int cost[MAX][MAX];
 
int dijkstra(){
  priority_queue<piii,vector<piii>,greater<piii> > Q;
  Q.push(piii(pii(0,0),0));
  fill(cost[0],cost[0]+MAX*MAX,INF);
  cost[0][0] = 0;
 
  while(!Q.empty()){
    piii p = Q.top(); Q.pop();
    int v = p.F.S, r = p.S;
    if(cost[v][r] < p.F.F) continue;
 
    if(r > 0){
      for(int i = 0 ; i < (int)G[v].size() ; i++){
        int to = G[v][i];
        if(cost[v][r] < cost[to][r-1]){
          cost[to][r-1] = cost[v][r];
          Q.push(piii(pii(cost[to][r-1],to),r-1));
        }
      }
    }
    pii t = taxi[v];
    for(int i = 0 ; i < (int)G[v].size() ; i++){
      int to = G[v][i];
      if(cost[v][r] + t.F < cost[to][t.S-1]){
        cost[to][t.S-1] = cost[v][r] + t.F;
        Q.push(piii(pii(cost[to][t.S-1],to),t.S-1));
      }
    }
  }
   
  return *min_element(cost[N-1],cost[N-1]+N);
}
 
int main(){
  int C,R,A,B;
  cin >> N >> K;
  for(int i = 0 ; i < N ; i++){
    cin >> C >> R;
    taxi[i] = pii(C,R);
  }
  for(int i = 0 ; i < K ; i++){
    cin >> A >> B; A--; B--;
    G[A].push_back(B);
    G[B].push_back(A);
  }
  cout << dijkstra() << endl;
  return 0;
}