Submission #1246392

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
#define F first
#define S second
vector<P> G[114514];
int dp[114514];
signed main(){
  int n,m,s,d;
  cin>>n>>m>>s>>d;
  int a[n],b[n],c[n];
  for(int i=0;i<n;i++) cin>>a[i]>>b[i]>>c[i];
  int x[m],y[m],t[m];
  for(int i=0;i<m;i++) cin>>x[i]>>y[i]>>t[i];
  for(int i=0;i<m;i++){
    x[i]--;y[i]--;
    G[x[i]].emplace_back(y[i],t[i]);
    G[y[i]].emplace_back(x[i],t[i]);
  }
  int INF=1LL<<55LL;
  for(int i=0;i<114514;i++) dp[i]=INF;
  priority_queue<P> q;
  s--;d--;
  q.emplace(0,s);
  dp[s]=0;
  while(!q.empty()){
    P p=q.top();q.pop();
    int d=-p.F,v=p.S;
    if(dp[v]<d) continue;
    int nd=dp[v];
    if(nd<=c[v]) nd=c[v];
    else{
      int k=(nd-c[v])%(a[v]+b[v]);
      if(k>=a[v]) nd+=a[v]+b[v]-k;
    }
    for(P e:G[v]){
      int u=e.F,nc=e.S;
      if(nd+nc<dp[u]){
	dp[u]=nd+nc;
	q.emplace(-dp[u],u);
      }
    }
  }
  cout<<dp[d]<<endl;
  return 0;
}

Submission Info

Judge Result