Submission #79993

ソースコード

?
1
2
3
4
#include<bits/stdc++.h>
#define V vector
#define L long
using namespace std;main(){L n,m,u,v,a,b,c,i=0,r;cin>>n>>m>>u>>v;n++;V<V<pair<L,L>>>s(n,V<pair<L,L>>());for(;i<m;i++)cin>>a>>b>>c,s[a].push_back({b,c}),s[b].push_back({a,c});queue<L>q;q.push(u);V<L>t(n,1e15);V<L>M(n);t[u]=0;while(q.size()){r=q.front();q.pop();for(i=0;i<s[r].size();i++)t[s[r][i].first]>t[r]+s[r][i].second?t[s[r][i].first]=t[r]+s[r][i].second,q.push(s[r][i].first),M[s[r][i].first]=r:0;}cout<<t[v]<<"\n";r=v;V<L>d;for(;r;r=M[r])d.push_back(r);for(i=d.size()-1;i>=0;i--){cout<<d[i];if(i)cout<<" ";}cout<<"\n";}

ステータス

項目 データ
問題 1814 - 最長経路問題
ユーザー名 woody_1227
投稿日時 2024-07-18 11:19:17
言語 C++17
状態 Accepted
得点 100
ソースコード長 585 Byte
最大実行時間 101 ms
最大メモリ使用量 11060 KB

セット

セット 得点 Cases
1 ALL 100 / 100 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
01.in AC 28 ms 604 KB
1
02.in AC 20 ms 448 KB
1
03.in AC 20 ms 416 KB
1
04.in AC 20 ms 512 KB
1
05.in AC 23 ms 604 KB
1
06.in AC 95 ms 10668 KB
1
07.in AC 59 ms 8548 KB
1
08.in AC 60 ms 8032 KB
1
09.in AC 35 ms 5948 KB
1
10.in AC 45 ms 6680 KB
1
11.in AC 35 ms 6588 KB
1
12.in AC 30 ms 5876 KB
1
13.in AC 19 ms 5160 KB
1
14.in AC 38 ms 6348 KB
1
15.in AC 56 ms 7680 KB
1
16.in AC 93 ms 11060 KB
1
17.in AC 89 ms 9844 KB
1
18.in AC 37 ms 6596 KB
1
19.in AC 78 ms 9604 KB
1
20.in AC 40 ms 7388 KB
1
21.in AC 101 ms 10860 KB
1
22.in AC 101 ms 10908 KB
1
23.in AC 96 ms 10808 KB
1
24.in AC 96 ms 10848 KB
1
25.in AC 92 ms 10896 KB
1