提出 #12957622

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define INF 2100000000
#define LLINF 10000000000000000ll
#define MOD 1000000007

bool dbgflag =false; //debug

struct edge {
  int cost;
  int to;
};


const int MAX_N = 5000;
int n;
vector<edge> graph[MAX_N];
int d[MAX_N];

void dijkstra(int s) {
  fill(d, d+n, INF);
  priority_queue<pll, vector<pll>, greater<pll>> que;

  d[s] = 0;
  que.push(pll(0, s));

  while(!que.empty()) {
    pll p = que.top();
    que.pop();
    ll v = p.second;

    if (d[v] < p.first) continue;

    for (edge e: graph[v]) {
      if (d[e.to] <= d[v] + e.cost) continue;
      d[e.to] = d[v] + e.cost;
      que.push(pll(d[e.to], e.to));
    }
  }
  return;
}


int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int k;
  cin >> n >> k;
  vector<pii> taxi(n);
  for (int i = 0; i < n; i++) {
    int c, r;
    cin >> c >> r;
    taxi[i] = pii(c, r);
  }

  vector<edge> taxiGraph[MAX_N];
  for (int i = 0; i < k; i++) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    edge e1, e2;
    e1.to = a; e1.cost = INF;
    e2.to = b; e2.cost = INF;
    taxiGraph[a].push_back(e2);
    taxiGraph[b].push_back(e1);
  }
  
  vector<vector<int>> roads(n, vector<int>(n,-1));
  for (int j = 0; j < n; j++) {
    queue<int> que;
    roads[j][j] = 0;
    que.push(j);
    while (!que.empty()) {
      int q = que.front();
      que.pop();
      for (int i = 0; i < taxiGraph[q].size(); i++) {
        int next_q = taxiGraph[q][i].to;
        if (roads[j][next_q] != -1) continue;
        roads[j][next_q] = roads[j][q] + 1;
        que.push(next_q);
      }
    }
  }

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if ((roads[i][j] <= taxi[i].second) && (i != j)) {
        edge e;
        e.cost = taxi[i].first; e.to = j;
        graph[i].push_back(e);
      }
    }
  }
  if (dbgflag) {
    for (int i = 0; i < n; i++) {
      cout << "i: " << i << endl;
      for (edge e: graph[i]) cout << e.to << " " << e.cost << endl;
    }
  }

  dijkstra(0);

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

提出情報

ジャッジ結果