結果

問題 No.3393 Move on Highway
コンテスト
ユーザー kino0402
提出日時 2025-11-29 17:01:24
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 1,307 ms / 3,000 ms
コード長 813 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,509 ms
コンパイル使用メモリ 289,884 KB
実行使用メモリ 99,028 KB
最終ジャッジ日時 2025-11-29 17:01:56
合計ジャッジ時間 31,830 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:1:2: warning: #import is a deprecated GCC extension [-Wdeprecated]
    1 | #import<bits/stdc++.h>
      |  ^~~~~~
main.cpp:23:1: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type]
   23 | main(){
      | ^~~~

ソースコード

diff #
raw source code 

#import<bits/stdc++.h>
#define r(n)for(l i=0;i<n;i++)
#define p push_back
using namespace std;
using l=long;
using pl=pair<l,l>;
vector<l> D(l N,l S,auto G){
  vector<l>d(N,1e18),v(N);
  priority_queue<pl,vector<pl>,greater<pl>>Q;
  d[S]=0;
  Q.push({0,S});
  while(!Q.empty()){
    l p=Q.top().second;Q.pop();
    if(v[p])continue;
    v[p]=1;
    for(auto[n,c]:G[p])if(d[n]>d[p]+c){
      d[n]=d[p]+c;
      Q.push({d[n],n});
    }
  }
  return d;
}
main(){
  l n,m,c,u,v,w;
  cin>>n>>m>>c;
  vector<vector<pl>>g(n),G(n*2);
  r(m){
    cin>>u>>v>>w;
    u--;v--;
    g[u].p({v,w+c});g[v].p({u,w+c});
    G[u].p({v,w+c});G[v].p({u,w+c});
    G[u].p({v+n,c});G[v].p({u+n,c});
    G[u+n].p({v+n,w+c});G[v+n].p({u+n,w+c});
  }
  vector<l>a=D(n,0,g),b=D(n*2,n-1,G);
  r(n-1)cout<<min(a[n-1],a[i+1]+b[i+1+n])<<endl;
}
0