Submission #00371

ソースコード

?
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <iostream>
#include <vector>
#include <queue>
#define INF 1e10;
using namespace std;
struct edge {
int to;
long long cost;
edge(int _to, long long _cost) {
to = _to;
cost = _cost;
}
};
typedef pair<long long, int> P;
vector<edge> G[100000];
long long d[100000];
int prev_route[100000];
int N, M, A, B;
void dijkstra(int s) {
priority_queue<P, vector<P>, greater<P> > que;
for (int i = 0; i < N; ++i) {
d[i] = (int) INF;
prev_route[i] = -1;
}
d[s] = 0LL;
que.push(P(0LL, s));
while (!que.empty()) {
P p = que.top();
que.pop();
int v = p.second;
if (d[v] < p.first) continue;
for (int i = 0; i < G[v].size(); ++i) {
edge e = G[v][i];
if (d[e.to] > d[v] + e.cost) {
d[e.to] = d[v] + e.cost;
que.push(P(d[e.to], e.to));
prev_route[e.to] = v;
}
}
}
}
vector<int> railway_city;
void get_path(int t) { //頂点tへの最短路
for (; t != -1; t = prev_route[t]) {
railway_city.push_back(t);
}
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
cin >> N >> M >> A >> B;
--A;
--B;
for (int i = 0; i < M; ++i) {
int u, v;
long long t;
cin >> u >> v >> t;
--u;
--v;
G[u].push_back(edge(v, t));
G[v].push_back(edge(u, t));
}
dijkstra(A); // A-Bの最短路を求める
get_path(B); // 最短路を復元
for (int i = 0; i < railway_city.size() - 1; ++i) {
for (int j = 0; j < G[railway_city[i]].size(); ++j) {
if (G[railway_city[i]][j].to == railway_city[i + 1]) {
G[railway_city[i]][j].cost = 0;
}
}
for (int j = 0; j < G[railway_city[i + 1]].size(); ++j) {
if (G[railway_city[i + 1]][j].to == railway_city[i]) {
G[railway_city[i + 1]][j].cost = 0;
}
}
}
dijkstra(A);
long long ans = 0;
for (int i = 0; i < N; ++i) {
ans += d[i];
}
cout << ans << endl;
}

ステータス

項目 データ
問題 0004 - railway
ユーザー名 pinebooks
投稿日時 2017-11-26 14:55:17
言語 C++11
状態 Wrong Answer
得点 0
ソースコード長 2253 Byte
最大実行時間 117 ms
最大メモリ使用量 14764 KB

セット

セット 得点 Cases
1 ALL 0 / 80 *
2 partial_1 0 / 20 !*, *S*

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
!test01.txt AC 18 ms 2784 KB
1
2
!test02.txt AC 20 ms 2956 KB
1
2
mesh_01.txt AC 57 ms 11760 KB
1
mesh_02.txt AC 56 ms 11792 KB
1
randomL_01.txt WA 95 ms 14728 KB
1
randomL_02.txt WA 94 ms 14764 KB
1
randomL_03.txt WA 93 ms 14692 KB
1
randomL_04.txt WA 95 ms 14540 KB
1
randomL_05.txt WA 117 ms 14644 KB
1
randomS_01.txt WA 18 ms 3064 KB
1
2
randomS_02.txt WA 17 ms 3068 KB
1
2
randomS_03.txt WA 18 ms 2944 KB
1
2
treeL_01.txt AC 83 ms 9096 KB
1
treeL_02.txt WA 51 ms 9092 KB
1
treeS_01.txt AC 24 ms 2884 KB
1
2
treeS_02.txt WA 20 ms 2980 KB
1
2