Submission #75867

ソースコード

?
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
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
using namespace std;
// テストケース修正後
typedef struct {
int town;
int hour;
int wait;
} Edge;
typedef struct {
long long cost;
int town;
} Node;
long long INF = 1e15;
int main() {
int n, m;
int u, v, h, w;
vector<vector<Edge>> g;
vector<long long> travel;
long long cost, next_cost;
int town;
Node top;
int ans;
auto cmp = [](const Node l, const Node r) -> bool {
if (l.cost != r.cost) return l.cost > r.cost;
return l.town < r.town;
}; // コストが少ないものから取り出すようにラムダ式を与える
priority_queue<Node, vector<Node>, decltype(cmp)> pque(cmp);
cin >> n >> m;
g.assign(n, vector<Edge>());
travel.assign(n, INF);
for (int i=0; i<m; i++) {
cin >> u >> v >> h >> w;
u--;
v--;
g[u].push_back((Edge){v, h, w});
g[v].push_back((Edge){u, h, w});
}
// ダイクストラ
pque.push((Node){0, 0});
while (!pque.empty()) {
top = pque.top();
cost = top.cost;
town = top.town;
pque.pop();
if (travel[town] < INF) continue;
travel[town] = cost;
for (Edge e : g[town]) {
next_cost = max(cost, (long long)e.wait) + e.hour;
pque.push((Node){next_cost, e.town});
}
}
ans = 0;
for (int i=1; i<n; i++) {
if (travel[ans] < travel[i] && travel[i] < INF) {
ans = i;
}
}
cout << ans+1 << endl;
return 0;
}

ステータス

項目 データ
問題 1659 - Yet Unavailable Roads
ユーザー名 ei1929
投稿日時 2023-09-10 14:25:49
言語 C++14
状態 Accepted
得点 1
ソースコード長 1491 Byte
最大実行時間 148 ms
最大メモリ使用量 9100 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
corner_input00.txt AC 106 ms 9100 KB
1
corner_input01.txt AC 105 ms 8836 KB
1
corner_input02.txt AC 104 ms 7360 KB
1
random_input01.txt AC 23 ms 688 KB
1
random_input02.txt AC 25 ms 628 KB
1
random_input03.txt AC 31 ms 564 KB
1
random_input04.txt AC 20 ms 580 KB
1
random_input05.txt AC 21 ms 504 KB
1
random_input06.txt AC 21 ms 588 KB
1
random_input07.txt AC 32 ms 600 KB
1
random_input08.txt AC 19 ms 768 KB
1
random_input09.txt AC 29 ms 1288 KB
1
random_input10.txt AC 21 ms 1096 KB
1
random_input11.txt AC 26 ms 1288 KB
1
random_input12.txt AC 31 ms 1344 KB
1
random_input13.txt AC 27 ms 1028 KB
1
random_input14.txt AC 27 ms 1356 KB
1
random_input15.txt AC 31 ms 1124 KB
1
random_input16.txt AC 31 ms 912 KB
1
random_input17.txt AC 104 ms 5532 KB
1
random_input18.txt AC 107 ms 6048 KB
1
random_input19.txt AC 80 ms 4960 KB
1
random_input20.txt AC 50 ms 2680 KB
1
random_input21.txt AC 138 ms 7956 KB
1
random_input22.txt AC 138 ms 8292 KB
1
random_input23.txt AC 47 ms 2912 KB
1
random_input24.txt AC 54 ms 2660 KB
1
random_input25.txt AC 143 ms 8464 KB
1
random_input26.txt AC 148 ms 8908 KB
1
random_input27.txt AC 116 ms 7352 KB
1
random_input28.txt AC 124 ms 7684 KB
1
sample_input01.txt AC 32 ms 536 KB
1
sample_input02.txt AC 19 ms 764 KB
1
sample_input03.txt AC 19 ms 604 KB
1
sample_input04.txt AC 22 ms 576 KB
1
sample_input05.txt AC 19 ms 676 KB
1