#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<set>
using namespace std;
typedef long long llint;
const int MAXN = 100005;
const int MAXM = 200005;
const llint INF = 1000000000000000000LL;
llint n, m, s, t, uu, vv, sol = INF;
llint a[MAXM], b[MAXM], c[MAXM], dist[3*MAXN], bio[MAXN], ok[MAXM];
vector < pair <int, int> > v[MAXN], r[MAXN], p[MAXN];
set < pair <llint, llint> > st;
void obrni () {
for (int i=1; i<=n; i++) {
p[i].clear();
}
for (int i=1; i<=n; i++) {
for (int j=0; j<r[i].size(); j++) {
p[r[i] [j].first].push_back(make_pair(i, 0));
}
}
for (int i=1; i<=n; i++) {
r[i] = p[i];
}
}
bool dfs (int x) {
if (x == s) return 1;
if (bio[x] != -1) return bio[x];
bio[x] = 0;
for (int i=0; i<r[x].size(); i++) {
int sus = r[x] [i].first;
int ind = r[x] [i].second;
ok[ind] = dfs(sus);
bio[x] |= ok[ind];
}
return bio[x];
}
void filter () {
memset(bio, -1, sizeof bio);
dfs(t);
for (int i=1; i<=n; i++) {
for (int j=0; j<r[i].size(); j++) {
if (ok[r[i] [j].second]) p[i].push_back(r[i] [j]);
}
}
for (int i=1; i<=n; i++) {
r[i] = p[i];
}
}
void dijkstra1 () {
for (int i=1; i<=n; i++) {
dist[i] = (i == s) ? 0LL : INF;
}
st.insert(make_pair(0, s));
while (!st.empty()) {
int cvor = st.begin() -> second;
st.erase(st.begin());
for (int i=0; i<v[cvor].size(); i++) {
int sus = v[cvor] [i].first;
int ind = v[cvor] [i].second;
if (dist[cvor] + c[ind] < dist[sus]) {
if (dist[sus] != INF) st.erase(make_pair(dist[sus], sus));
dist[sus] = dist[cvor] + c[ind];
st.insert(make_pair(dist[sus], sus));
r[sus].clear();
}
if (dist[cvor] + c[ind] == dist[sus]) r[sus].push_back(make_pair(cvor, ind));
}
}
}
void dijkstra2 () {
for (int i=1; i<=n; i++) {
for (int j=0; j<3; j++) {
int cvor = i + j*MAXN;
if (cvor == uu) dist[cvor] = 0; else dist[cvor] = INF;
}
}
st.insert(make_pair(0, uu));
while (!st.empty()) {
int all = (st.begin() -> second);
int tip = all / MAXN;
int cvor = all % MAXN;
st.erase(st.begin());
for (int i=0; i<v[cvor].size(); i++) {
int sus = v[cvor] [i].first;
int ind = v[cvor] [i].second;
if (tip == 1 || tip == 2) sus += 2*MAXN;
if (dist[all] + c[ind] < dist[sus]) {
if (dist[sus] != INF) st.erase(make_pair(dist[sus], sus));
dist[sus] = dist[all] + c[ind];
st.insert(make_pair(dist[sus], sus));
}
}
if (tip == 2) continue;
for (int i=0; i<r[cvor].size(); i++) {
int sus = r[cvor] [i].first + MAXN;
if (dist[all] < dist[sus]) {
if (dist[sus] != INF) st.erase(make_pair(dist[sus], sus));
dist[sus] = dist[all];
st.insert(make_pair(dist[sus], sus));
}
}
}
sol = min(sol, dist[vv]);
sol = min(sol, dist[vv + MAXN]);
sol = min(sol, dist[vv + MAXN*2]);
}
int main () {
cin >> n >> m >> s >> t >> uu >> vv;
for (int i=0; i<m; i++) {
scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);
v[a[i]].push_back(make_pair(b[i], i));
v[b[i]].push_back(make_pair(a[i], i));
}
dijkstra1();
filter();
dijkstra2();
obrni();
dijkstra2();
cout << sol;
return 0;
}
Compilation message
commuter_pass.cpp: In function 'void obrni()':
commuter_pass.cpp:25:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j=0; j<r[i].size(); j++) {
~^~~~~~~~~~~~
commuter_pass.cpp: In function 'bool dfs(int)':
commuter_pass.cpp:38:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<r[x].size(); i++) {
~^~~~~~~~~~~~
commuter_pass.cpp: In function 'void filter()':
commuter_pass.cpp:51:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j=0; j<r[i].size(); j++) {
~^~~~~~~~~~~~
commuter_pass.cpp: In function 'void dijkstra1()':
commuter_pass.cpp:68:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<v[cvor].size(); i++) {
~^~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dijkstra2()':
commuter_pass.cpp:95:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<v[cvor].size(); i++) {
~^~~~~~~~~~~~~~~
commuter_pass.cpp:106:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<r[cvor].size(); i++) {
~^~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:123:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1400 ms |
30840 KB |
Output is correct |
2 |
Correct |
1483 ms |
34836 KB |
Output is correct |
3 |
Correct |
1446 ms |
44256 KB |
Output is correct |
4 |
Correct |
1508 ms |
44256 KB |
Output is correct |
5 |
Correct |
1119 ms |
48412 KB |
Output is correct |
6 |
Correct |
1427 ms |
49616 KB |
Output is correct |
7 |
Correct |
1402 ms |
56084 KB |
Output is correct |
8 |
Correct |
1403 ms |
59052 KB |
Output is correct |
9 |
Correct |
1274 ms |
59052 KB |
Output is correct |
10 |
Correct |
737 ms |
63896 KB |
Output is correct |
11 |
Correct |
523 ms |
63896 KB |
Output is correct |
12 |
Correct |
1398 ms |
69412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1560 ms |
73592 KB |
Output is correct |
2 |
Correct |
1297 ms |
76364 KB |
Output is correct |
3 |
Correct |
1348 ms |
81476 KB |
Output is correct |
4 |
Correct |
1292 ms |
83252 KB |
Output is correct |
5 |
Correct |
1162 ms |
87432 KB |
Output is correct |
6 |
Correct |
1119 ms |
94416 KB |
Output is correct |
7 |
Correct |
1769 ms |
100492 KB |
Output is correct |
8 |
Correct |
1403 ms |
100492 KB |
Output is correct |
9 |
Correct |
1300 ms |
101816 KB |
Output is correct |
10 |
Correct |
1346 ms |
104320 KB |
Output is correct |
11 |
Correct |
490 ms |
104320 KB |
Output is correct |
12 |
Correct |
1416 ms |
114472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
114472 KB |
Output is correct |
2 |
Correct |
9 ms |
114472 KB |
Output is correct |
3 |
Correct |
12 ms |
114472 KB |
Output is correct |
4 |
Correct |
37 ms |
114472 KB |
Output is correct |
5 |
Correct |
30 ms |
114472 KB |
Output is correct |
6 |
Correct |
41 ms |
114472 KB |
Output is correct |
7 |
Correct |
15 ms |
114472 KB |
Output is correct |
8 |
Correct |
13 ms |
114472 KB |
Output is correct |
9 |
Correct |
13 ms |
114472 KB |
Output is correct |
10 |
Correct |
24 ms |
114472 KB |
Output is correct |
11 |
Correct |
11 ms |
114472 KB |
Output is correct |
12 |
Correct |
10 ms |
114472 KB |
Output is correct |
13 |
Correct |
11 ms |
114472 KB |
Output is correct |
14 |
Correct |
14 ms |
114472 KB |
Output is correct |
15 |
Correct |
12 ms |
114472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1400 ms |
30840 KB |
Output is correct |
2 |
Correct |
1483 ms |
34836 KB |
Output is correct |
3 |
Correct |
1446 ms |
44256 KB |
Output is correct |
4 |
Correct |
1508 ms |
44256 KB |
Output is correct |
5 |
Correct |
1119 ms |
48412 KB |
Output is correct |
6 |
Correct |
1427 ms |
49616 KB |
Output is correct |
7 |
Correct |
1402 ms |
56084 KB |
Output is correct |
8 |
Correct |
1403 ms |
59052 KB |
Output is correct |
9 |
Correct |
1274 ms |
59052 KB |
Output is correct |
10 |
Correct |
737 ms |
63896 KB |
Output is correct |
11 |
Correct |
523 ms |
63896 KB |
Output is correct |
12 |
Correct |
1398 ms |
69412 KB |
Output is correct |
13 |
Correct |
1560 ms |
73592 KB |
Output is correct |
14 |
Correct |
1297 ms |
76364 KB |
Output is correct |
15 |
Correct |
1348 ms |
81476 KB |
Output is correct |
16 |
Correct |
1292 ms |
83252 KB |
Output is correct |
17 |
Correct |
1162 ms |
87432 KB |
Output is correct |
18 |
Correct |
1119 ms |
94416 KB |
Output is correct |
19 |
Correct |
1769 ms |
100492 KB |
Output is correct |
20 |
Correct |
1403 ms |
100492 KB |
Output is correct |
21 |
Correct |
1300 ms |
101816 KB |
Output is correct |
22 |
Correct |
1346 ms |
104320 KB |
Output is correct |
23 |
Correct |
490 ms |
104320 KB |
Output is correct |
24 |
Correct |
1416 ms |
114472 KB |
Output is correct |
25 |
Correct |
34 ms |
114472 KB |
Output is correct |
26 |
Correct |
9 ms |
114472 KB |
Output is correct |
27 |
Correct |
12 ms |
114472 KB |
Output is correct |
28 |
Correct |
37 ms |
114472 KB |
Output is correct |
29 |
Correct |
30 ms |
114472 KB |
Output is correct |
30 |
Correct |
41 ms |
114472 KB |
Output is correct |
31 |
Correct |
15 ms |
114472 KB |
Output is correct |
32 |
Correct |
13 ms |
114472 KB |
Output is correct |
33 |
Correct |
13 ms |
114472 KB |
Output is correct |
34 |
Correct |
24 ms |
114472 KB |
Output is correct |
35 |
Correct |
11 ms |
114472 KB |
Output is correct |
36 |
Correct |
10 ms |
114472 KB |
Output is correct |
37 |
Correct |
11 ms |
114472 KB |
Output is correct |
38 |
Correct |
14 ms |
114472 KB |
Output is correct |
39 |
Correct |
12 ms |
114472 KB |
Output is correct |
40 |
Correct |
1648 ms |
118600 KB |
Output is correct |
41 |
Correct |
1311 ms |
118600 KB |
Output is correct |
42 |
Correct |
1267 ms |
118600 KB |
Output is correct |
43 |
Correct |
685 ms |
121256 KB |
Output is correct |
44 |
Correct |
732 ms |
122508 KB |
Output is correct |
45 |
Correct |
1422 ms |
133844 KB |
Output is correct |
46 |
Correct |
1519 ms |
137356 KB |
Output is correct |
47 |
Correct |
1514 ms |
137588 KB |
Output is correct |
48 |
Correct |
718 ms |
137588 KB |
Output is correct |
49 |
Correct |
1242 ms |
148152 KB |
Output is correct |
50 |
Correct |
1407 ms |
150556 KB |
Output is correct |
51 |
Correct |
1338 ms |
155808 KB |
Output is correct |