AOJ 0596 Taxis

問題ページ
タクシー | Aizu Online Judge

考えたこと

最短距離と言われたのでdijkstraを考える。遷移先が距離r[i]以下の頂点であるdijkstraをすればよさそう。全頂点からそれぞれdijkstraをしてある頂点から距離がr[i]以下の点を全列挙しておけば、あとはdijkstraでよさそう。前処理にO(EVlogV)で大体1*10^8くらいになりそうだけどTLが8secで緩いのでこれでも通りそうと思い投げたら通った。

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int c[5010], r[5010];

struct edge{int to, cost;};

int n, d[5010];
vector<edge> g[5010];
VI v[5010];

void dijkstra(int s) {
  priority_queue<PII, vector<PII>, greater<PII>> que;
  fill(d, d+n, INF);
  d[s] = 0;
  que.push(PII{0, s});

  while(que.size()) {
    PII p = que.top(); que.pop();
    int v = p.second;
    if(d[v] < p.first) continue;
    for(edge e: g[v]) {
      if(d[e.to] > d[v] + e.cost) {
        d[e.to] = d[v] + e.cost;
        que.push(PII{d[e.to], e.to});
      }
    }
  }
  REP(i, n) if(d[i] <= r[s]) v[s].PB(i);
}

void dijkstra2(int s) {
  priority_queue<PII, vector<PII>, greater<PII>> que;
  fill(d, d+n, INF);
  d[s] = 0;
  que.push(PII{0, s});

  while(que.size()) {
    PII p = que.top(); que.pop();
    int vv = p.second;
    if(d[vv] < p.first) continue;
    for(int i: v[vv]) {
      if(d[i] > d[vv] + c[vv]) {
        d[i] = d[vv] + c[vv];
        que.push(PII{d[i], i});
      }
    }
  }
  cout << d[n-1] << endl;
}

signed main(void)
{
  int k;
  cin >> n >> k;
  REP(i, n) cin >> c[i] >> r[i];
  REP(i, k) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    g[x].PB({y, 1});
    g[y].PB({x, 1});
  }

  REP(i, n) dijkstra(i);
  dijkstra2(0);

  return 0;
}