Submission #00004

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;
#define int long long
/*
n頂点(1~n)m辺の重み付き無向グラフの最短経路の復元
*/
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>q;
main(){
int n,m,r,l;cin>>n>>m;
r=1;l=n;
//cin>>r;//始点の設定 (初期設定は　１　)
//cin>>l;//終点の設定 (初期設定は　n 　)
vector<vector<pair<int,int>>>s(n+1,vector<pair<int,int>>(0));
for(int i=0;i<m;i++){
int a,b,c;cin>>a>>b>>c;
s[a].push_back(make_pair(c,b));
}
vector<int>cos(n+1,LONG_LONG_MAX);
vector<bool>af(n+1,false);
vector<int>w(n+1,-1);
q.push(make_pair(0,r));//スタート地点の変更
cos[r]=0;//スタート地点の変更
while(!q.empty()){
int u=q.top().first;
int v=q.top().second;
q.pop();
if(af[v]){
continue;
}
for(int i=0;i<s[v].size();i++){
if(!af[s[v][i].second]){
if(cos[s[v][i].second]>cos[v]+s[v][i].first){
cos[s[v][i].second]=cos[v]+s[v][i].first;
w[s[v][i].second]=v;
q.push(make_pair(cos[s[v][i].second],s[v][i].second));
}
}
}
af[v]=true;
}
if(cos[n]==LONG_LONG_MAX){
cout<<"-1\n";
}else{
cout<<cos[n]<<"\n";
}
}

ステータス

項目 データ
問題 0003 - Shortest Path1
ユーザー名 ei2326
投稿日時 2024-08-09 10:04:23
言語 C++17
状態 Accepted
得点 10
ソースコード長 1438 Byte
最大実行時間 91 ms
最大メモリ使用量 7648 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1.txt AC 20 ms 604 KB
1
in2.txt AC 21 ms 704 KB
1
in3.txt AC 24 ms 552 KB
1
in4.txt AC 20 ms 524 KB
1
in5.txt AC 23 ms 880 KB
1
in6.txt AC 25 ms 900 KB
1
in7.txt AC 27 ms 776 KB
1
in8.txt AC 79 ms 4076 KB
1
in9.txt AC 91 ms 7648 KB
1