Submission #63291479

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'
using ll = long long;
using P = pair<ll,ll>;
const int INF = numeric_limits<int>::max();
const ll LINF = 1e18; // numeric_limits<ll>::max();
const int MOD = 1e9+7;

int main() {
  int n,m; ll x; cin >> n >> m >> x;
  vector gf(n,vector<int>());
  vector gb(n,vector<int>()); // back
  REP(i,m) {
    int u,v; cin >> u >> v; u--; v--;
    gf[u].push_back(v);
    gb[v].push_back(u);
  }

  auto calc_id = [](int id, int state) {
    return id * 2 + state;
  };

  vector<vector<P>> edges(2*n);
  REP(v,n) {
    for(auto u : gf[v]) edges[calc_id(v,0)].emplace_back(calc_id(u,0), 1LL);
    for(auto u : gb[v]) edges[calc_id(v,1)].emplace_back(calc_id(u,1), 1LL);
    edges[calc_id(v,0)].emplace_back(calc_id(v,1), x);
    edges[calc_id(v,1)].emplace_back(calc_id(v,0), x);
  }

  priority_queue<P, vector<P>, greater<P>> pq;
  pq.emplace(0,calc_id(0,0));

  vector<ll> dist(2*n,LINF);
  while(pq.size()) {
    auto [cd,id] = pq.top(); pq.pop();
    if (dist[id] < cd) continue;

    for(auto nx: edges[id]) {
      auto [nxt,cost] = nx;
      ll nd = cd + cost;
      if (dist[nxt] > nd) {
        dist[nxt] = nd;
        pq.emplace(nd,nxt);
      }
    }
  }

  ll ans = min(dist[calc_id(n-1,0)],dist[calc_id(n-1,1)]);
  cout << ans << endl;
  return 0;
}

Submission Info

Judge Result