TakahiroNakamori

TakahiroNakamori

ナカモリタカヒロ

 
 

Train

問題

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

記録

解法

コード例

#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;
}