結果

問題 No.3712 Urban Train
コンテスト
ユーザー kukone
提出日時 2026-09-11 23:07:00
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 237 ms / 2,000 ms
+ 104µs
コード長 1,606 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,028 ms
コンパイル使用メモリ 381,904 KB
実行使用メモリ 20,920 KB
最終ジャッジ日時 2026-09-11 23:07:13
合計ジャッジ時間 8,760 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#ifndef ONLINE_JUDGE
// #define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll=long long;
using ld=long double;
using st=string;
using P=pair<ll,ll>;
typedef atcoder::modint mint;
ll inf=9e18;
template<typename T, int s, int i = 0>
auto vec(const ll (&sizes)[s], const T& init = T()){
  if constexpr(i < s) return vector(sizes[i], vec<T, s, i+1>(sizes, init));
  else return init;
}


struct Edge{ll to,cost=1;};
bool operator>(Edge a,Edge b){
  return a.cost>b.cost;
}
vector<ll> a0,a1,a2;
void dijkstra(vector<vector<Edge>> &graph,ll s,vector<ll> &dis){
  priority_queue<Edge,vector<Edge>,greater<Edge>> q;
  dis=vector<ll>(graph.size(),inf);
  q.push({s,a0[s]});
  dis[s]=a0[s];
  while(!q.empty()){
    ll f=q.top().to,c=q.top().cost;
    // cout<<f+1<<" "<<c<<"\n";
    q.pop();
    if(f==graph.size()-1) return;
    if(dis[f]<c) continue;
    for(auto i:graph[f]){
      ll nec=min(((dis[f]-1)/a0[f]+1)*a0[f]+i.cost+(((dis[f]-1)/a0[f]+1)%a1[f]==0)*a2[f],((dis[f]-1)/a0[f]+2)*(a0[f])+i.cost);
      // cout<<i.to+1<<" "<<nec<<"a\n";
      if(dis[i.to]<nec) continue;
      dis[i.to]=nec;
      q.push({i.to,dis[i.to]});
    }
  }
}

int main(){
  ll n,m,u,v,c;
  cin>>n>>m;
  auto w=vec<Edge>({n,0},{0,0});
  a0=vec<ll>({n},0);
  a1=vec<ll>({n},0);
  a2=vec<ll>({n},0);
  for(ll i=0;i<m;i++){
    cin>>u>>v>>c;
    w[--u].push_back({--v,c});
    w[v].push_back({u,c});
  }
  for(ll i=0;i<n;i++) cin>>a0[i];
  for(ll i=0;i<n;i++) cin>>a1[i];
  for(ll i=0;i<n;i++) cin>>a2[i];
  auto dis=vec<ll>({n},0);
  dijkstra(w,0,dis);
  cout<<dis[n-1]<<"\n";
}
0