Submission #00369

ソースコード

?
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;
}

ステータス

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

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
!test_01.txt WA 22 ms 2784 KB
1
!test_02.txt RE 151 ms 2828 KB
1
random_01.txt RE 27 ms 2996 KB
1
random_02.txt WA 19 ms 2812 KB
1
random_03.txt RE 22 ms 2940 KB
1
random_04.txt RE 27 ms 2920 KB
1
random_05.txt RE 21 ms 2880 KB
1
random_06.txt WA 20 ms 2836 KB
1
random_07.txt WA 15 ms 2928 KB
1
random_08.txt WA 16 ms 3020 KB
1