Submission #58141

ソースコード

?
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
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;
#define read cin >>
#define echo cout <<
#define fin << '\n'
#define _ << ' ' <<
#define in :
#define var auto&&
struct DijkstraData {
int pos, cost;
bool operator < ( const DijkstraData &tar ) const {
return cost < tar.cost;
}
bool operator > ( const DijkstraData &tar ) const {
return cost > tar.cost;
}
};
vector<pair<int, int> > g[100100];
int dist[100100];
int dijkstra ( int start, int goal ) {
priority_queue<DijkstraData, vector<DijkstraData>, greater<DijkstraData> > p;
for ( int i = 0; i < 100100; i++ ) dist[i] = 0x3f3f3f3f;
dist[start] = 0;
p.push((DijkstraData){start, 0});
while ( !p.empty() ) {
DijkstraData now = p.top();
p.pop();
int cost = now.cost;
int pos = now.pos;
if ( dist[pos] != cost ) continue;
for ( int i = 0; i < (int)g[pos].size(); i++ ) {
int next = g[pos][i].first;
int ncst = g[pos][i].second + cost;
if ( ncst < dist[next] ) {
dist[next] = ncst;
p.push((DijkstraData){next, ncst});
}
}
}
return dist[goal];
}
signed main ( ) {
int v, e;
cin >> v >> e;
for ( int i = 0; i < e; i++ ) {
int a, b, c;
read a >> b >> c;
g[a].push_back(make_pair(b, c));
g[b].push_back(make_pair(a, c));
}
echo dijkstra(1, v) fin;
return 0;
}

ステータス

項目 データ
問題 1257 - ダイクストラ大好き厨とコーナーテストケース
ユーザー名 r1825
投稿日時 2020-01-15 15:52:33
言語 C++14
状態 Accepted
得点 5
ソースコード長 1526 Byte
最大実行時間 149 ms
最大メモリ使用量 9892 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
corner_input.txt AC 127 ms 8912 KB
1
input01.txt AC 149 ms 9892 KB
1
input02.txt AC 95 ms 7484 KB
1
input03.txt AC 103 ms 7164 KB
1
input04.txt AC 133 ms 8676 KB
1
input05.txt AC 108 ms 8744 KB
1
sample_input.txt AC 30 ms 3148 KB
1