Submission #1552039

---

Source Code Expand

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

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned __int128 HASH;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll,int> plli;
typedef pair<double, int> pdbi;
typedef pair<int,pii> pipii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()

const ll hmod1 = 999999937;
const ll hmod2 = 1000000000 + 9;
const ll INF = 1<<30;
const ll mod = 1000000000 + 7;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const double pi = 3.141592653589793;

int n, m, s, tar;
struct edge{int to, cost;};
vector<vector<edge>> g(100000+5);
int a[100000 + 5], b[100000 + 5], c[100000 + 5];

vector<ll> dijkstra(int s, int n, vector<vector<edge>>& g){
    priority_queue<plli, vector<plli>, greater<plli>> que;
    vector<ll> d(n, LLONG_MAX / 10); d[s] = 0;
    que.push(plli(0, s));

    while (!que.empty()){
        plli p = que.top();que.pop();
        int fr = p.second;
        if (d[fr] < p.first) continue;
        for (edge e: g[fr]){
            int ti = d[fr];
            int wait = 0;
            if (ti <= c[fr]) wait = c[fr] - ti;
            else {
                ti -= c[fr];
                ti %= (a[fr] + b[fr]);
                if (ti < a[fr]) wait = 0;
                else wait = b[fr] - (ti - a[fr]);
            }
            if (d[e.to] > d[fr] + wait + e.cost){
                d[e.to] = d[fr] + wait + e.cost;
                que.push(plli(d[e.to], e.to));
            }
        }
    }
    return d;
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m >> s >> tar;
    s--; tar--;
    rep(i, n) cin >> a[i] >> b[i] >> c[i];
    rep(i, m) {
        int x, y, t;
        cin >> x >> y >> t;
        x--; y--;
        g[x].push_back(edge{y, t});
        g[y].push_back(edge{x, t});
    }
    vector<ll> dist = dijkstra(s, n, g);
    cout << dist[tar] << endl;

}

Submission Info

Judge Result