問題

E – Train

プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

atcoder.jp

記録

• 2022/3/17　解法わからず。

解法

• ダイクストラ

コード例

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<ll, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
const ll INF = 1LL << 62;
// const int INF = 1001001001;

struct Edge {
  int to;
  ll cost;
  ll start;
};

int N, M, X, Y;

vector<vector<Edge>> graph;
vector<ll> dist;
priority_queue<P, vector<P>, greater<P>> pq;

void dijkstra() {
  while(!pq.empty()) {
    P p = pq.top();
    ll x = p.first;
    ll v = p.second;
    pq.pop();

    if(dist[v] < x) {
      continue;
    }

    for(int i = 0; i < int(graph[v].size()); ++i) {
      int to = graph[v][i].to;
      ll start = graph[v][i].start;
      ll cost = graph[v][i].cost;
      ll res = dist[v] % start;
      if(res != 0) {
        res = start - res;
      }
      if(dist[v] + cost + res < dist[to]) {
        dist[to] = dist[v] + cost + res;
        pq.push(make_pair(dist[to], to));
      }
    }
  }
  return;
}

int main() {
  cin >> N >> M >> X >> Y;
  X--;
  Y--;

  graph.resize(N);
  dist.resize(N);

  rep(i, M) {
    int A, B, T, K;
    cin >> A >> B >> T >> K;
    A--;
    B--;

    Edge e1;
    e1.to = B;
    e1.cost = T;
    e1.start = K;
    graph[A].push_back(e1);

    Edge e2;
    e2.to = A;
    e2.cost = T;
    e2.start = K;
    graph[B].push_back(e2);
  }

  rep(i, N) { dist[i] = INF; }

  pq.push(make_pair(0, X));
  dist[X] = 0;
  dijkstra();

  if(dist[Y] == INF) {
    cout << "-1" << endl;
  } else {
    cout << dist[Y] << endl;
  }
  return 0;
}