タクシー

0596.cpp

#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9 + 9;
const int max_n = 5000;
typedef pair<int, int> P;

struct edge{
  int to, cost;
};

int n, k;
int V;
vector<edge> G[max_n];
vector<int> g[max_n];

int d[max_n];
int c[max_n], r[max_n];
bool f[max_n];

void dijkstra()
{
  priority_queue<P, vector<P>, greater<P>> q;
  fill(d, d + n, inf);
  d[0] = 0;
  q.push(P(0, 0));

  while (!q.empty()){
    P p = q.top(); q.pop();

    int v = p.second;
    if (d[v] < p.first) continue;
    for (int i = 0; i < G[v].size(); i++){
      edge e = G[v][i];
      if (d[e.to] > d[v] + e.cost){
        d[e.to] = d[v] + e.cost;
        q.push(P(d[e.to], e.to));
      }
    }
  }
}

void bfs(int R, int v)
{
  if (R == 0) return;
  if (f[v] >= R) return;
  f[v] = R;

  edge e;
  e.to = v; e.cost = c[V];
  G[V].push_back(e);

  for (int i = 0; i < g[v].size(); i++){
    bfs(R - 1, g[v][i]);
  }
}

int main()
{
  cin >> n >> k;
  for (int i = 0; i < n; i++){
    cin >> c[i] >> r[i];
  }
  for (int i = 0; i < k; i++){
    int a, b;
    cin >> a >> b;
    a--; b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  for (int i = 0; i < n; i++){
    memset(f, false, sizeof(f));
    
    queue<P> que;
    que.push(P(i, r[i] + 1));
    while (!que.empty()){
      P p = que.front(); que.pop();
      int v = p.first;
      if (p.second == 0) continue;
      if (f[v]) continue;
      f[v] = true;

      edge e;
      e.to = v; e.cost = c[i];
      if (i != v) G[i].push_back(e);
      for (int j = 0; j < g[v].size(); j++){
        que.push(P(g[v][j], p.second - 1));
      }
    }
  }

  dijkstra();

  cout << d[n - 1] << endl;
}