///
/// "People's Dreams.. Never End!!"
///
/// ~Marshall D. Teach
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define mk make_pair
#define endl cout << '\n'
#define haha cerr << "haha\n"
#define all(x) x.begin(), x.end()
#define kill(x) exit((cout << (x) << '\n', 0))
#define yn(flag) ((flag) ? "YES\n": "NO\n")
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2")
ll const inf = 1'000'000'000'000'000 + 10;
ll const mod = 1'000'000'000 + 7;
ll const maxn = 300'000 + 10;
ll const base = 337;
ll const sq = 320;
ll n;
ll dis[maxn];
set<pll> s;
vector<pll> adj[maxn];
vector<ll> vec[maxn];
ll dij(ll x, ll y) {
fill(dis, dis + 3 * n, inf);
dis[x] = 0;
s.clear();
s.insert(mk(0, x));
while (s.size()) {
auto [d, v] = *s.begin();
s.erase(mk(d, v));
for (auto [u, w] : adj[v]) {
if (dis[u] > d + w) {
s.erase(mk(dis[u], u));
dis[u] = d + w;
s.insert({dis[u], u});
vec[u].clear();
vec[u].pb(v);
} else if (dis[u] == d + w) {
vec[u].pb(v);
}
}
}
return dis[y];
}
bool mark[maxn];
void build1() {
for (ll i = n; i < 2 * n; ++i) {
if (mark[i - n])
for (auto u : vec[i - n]) {
adj[u + n].pb({i, 0});
}
}
for (ll i = 2 * n; i < 3 * n; ++i) {
for (auto u : adj[i - 2 * n])
adj[i].pb({u.F + 2 * n, u.S});
}
for (ll i = 0; i < n; ++i) {
adj[i].pb({i + n, 0});
adj[i + n].pb({i + 2 * n, 0});
}
}
void dfs(ll v) {
mark[v] = true;
for (auto u : vec[v]) {
if (!mark[u])
dfs(u);
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
ll m;
cin >> n >> m;
ll a, b, u, v;
cin >> a >> b >> u >> v;
--a, --b, --u, --v;
for (ll i = 0; i < m; ++i) {
ll a, b, c;
cin >> a >> b >> c;
--a, --b;
adj[a].pb(mk(b, c));
adj[b].pb(mk(a, c));
}
dij(a, b);
dfs(b);
build1();
cout << min(dij(u, v + n + n), dij(v, u + n + n)) << '\n';
}
// check before submiting :
// maxn (please check this shit)
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1231 ms |
59952 KB |
Output is correct |
2 |
Correct |
1136 ms |
56564 KB |
Output is correct |
3 |
Correct |
1076 ms |
61452 KB |
Output is correct |
4 |
Correct |
1260 ms |
60460 KB |
Output is correct |
5 |
Correct |
1097 ms |
59076 KB |
Output is correct |
6 |
Correct |
1294 ms |
60020 KB |
Output is correct |
7 |
Correct |
1154 ms |
58388 KB |
Output is correct |
8 |
Correct |
1141 ms |
57944 KB |
Output is correct |
9 |
Correct |
1152 ms |
56984 KB |
Output is correct |
10 |
Correct |
885 ms |
58224 KB |
Output is correct |
11 |
Correct |
504 ms |
46528 KB |
Output is correct |
12 |
Correct |
1137 ms |
54928 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1228 ms |
58820 KB |
Output is correct |
2 |
Correct |
1250 ms |
57996 KB |
Output is correct |
3 |
Correct |
1133 ms |
57992 KB |
Output is correct |
4 |
Correct |
1194 ms |
58124 KB |
Output is correct |
5 |
Correct |
1210 ms |
57620 KB |
Output is correct |
6 |
Correct |
1086 ms |
60816 KB |
Output is correct |
7 |
Correct |
1175 ms |
59596 KB |
Output is correct |
8 |
Correct |
1172 ms |
57408 KB |
Output is correct |
9 |
Correct |
1213 ms |
58256 KB |
Output is correct |
10 |
Correct |
1216 ms |
57568 KB |
Output is correct |
11 |
Correct |
522 ms |
50244 KB |
Output is correct |
12 |
Correct |
1056 ms |
61232 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
17988 KB |
Output is correct |
2 |
Correct |
9 ms |
14552 KB |
Output is correct |
3 |
Correct |
9 ms |
14548 KB |
Output is correct |
4 |
Correct |
31 ms |
20920 KB |
Output is correct |
5 |
Correct |
19 ms |
17268 KB |
Output is correct |
6 |
Correct |
11 ms |
14552 KB |
Output is correct |
7 |
Correct |
11 ms |
14668 KB |
Output is correct |
8 |
Correct |
12 ms |
14796 KB |
Output is correct |
9 |
Correct |
10 ms |
14668 KB |
Output is correct |
10 |
Correct |
20 ms |
17504 KB |
Output is correct |
11 |
Correct |
9 ms |
14412 KB |
Output is correct |
12 |
Correct |
9 ms |
14412 KB |
Output is correct |
13 |
Correct |
9 ms |
14412 KB |
Output is correct |
14 |
Correct |
9 ms |
14540 KB |
Output is correct |
15 |
Correct |
9 ms |
14540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1231 ms |
59952 KB |
Output is correct |
2 |
Correct |
1136 ms |
56564 KB |
Output is correct |
3 |
Correct |
1076 ms |
61452 KB |
Output is correct |
4 |
Correct |
1260 ms |
60460 KB |
Output is correct |
5 |
Correct |
1097 ms |
59076 KB |
Output is correct |
6 |
Correct |
1294 ms |
60020 KB |
Output is correct |
7 |
Correct |
1154 ms |
58388 KB |
Output is correct |
8 |
Correct |
1141 ms |
57944 KB |
Output is correct |
9 |
Correct |
1152 ms |
56984 KB |
Output is correct |
10 |
Correct |
885 ms |
58224 KB |
Output is correct |
11 |
Correct |
504 ms |
46528 KB |
Output is correct |
12 |
Correct |
1137 ms |
54928 KB |
Output is correct |
13 |
Correct |
1228 ms |
58820 KB |
Output is correct |
14 |
Correct |
1250 ms |
57996 KB |
Output is correct |
15 |
Correct |
1133 ms |
57992 KB |
Output is correct |
16 |
Correct |
1194 ms |
58124 KB |
Output is correct |
17 |
Correct |
1210 ms |
57620 KB |
Output is correct |
18 |
Correct |
1086 ms |
60816 KB |
Output is correct |
19 |
Correct |
1175 ms |
59596 KB |
Output is correct |
20 |
Correct |
1172 ms |
57408 KB |
Output is correct |
21 |
Correct |
1213 ms |
58256 KB |
Output is correct |
22 |
Correct |
1216 ms |
57568 KB |
Output is correct |
23 |
Correct |
522 ms |
50244 KB |
Output is correct |
24 |
Correct |
1056 ms |
61232 KB |
Output is correct |
25 |
Correct |
21 ms |
17988 KB |
Output is correct |
26 |
Correct |
9 ms |
14552 KB |
Output is correct |
27 |
Correct |
9 ms |
14548 KB |
Output is correct |
28 |
Correct |
31 ms |
20920 KB |
Output is correct |
29 |
Correct |
19 ms |
17268 KB |
Output is correct |
30 |
Correct |
11 ms |
14552 KB |
Output is correct |
31 |
Correct |
11 ms |
14668 KB |
Output is correct |
32 |
Correct |
12 ms |
14796 KB |
Output is correct |
33 |
Correct |
10 ms |
14668 KB |
Output is correct |
34 |
Correct |
20 ms |
17504 KB |
Output is correct |
35 |
Correct |
9 ms |
14412 KB |
Output is correct |
36 |
Correct |
9 ms |
14412 KB |
Output is correct |
37 |
Correct |
9 ms |
14412 KB |
Output is correct |
38 |
Correct |
9 ms |
14540 KB |
Output is correct |
39 |
Correct |
9 ms |
14540 KB |
Output is correct |
40 |
Correct |
1328 ms |
62444 KB |
Output is correct |
41 |
Correct |
1155 ms |
56260 KB |
Output is correct |
42 |
Correct |
1140 ms |
56132 KB |
Output is correct |
43 |
Correct |
548 ms |
47428 KB |
Output is correct |
44 |
Correct |
539 ms |
47564 KB |
Output is correct |
45 |
Correct |
1065 ms |
60920 KB |
Output is correct |
46 |
Correct |
1071 ms |
61208 KB |
Output is correct |
47 |
Correct |
1345 ms |
58296 KB |
Output is correct |
48 |
Correct |
569 ms |
46808 KB |
Output is correct |
49 |
Correct |
1067 ms |
65280 KB |
Output is correct |
50 |
Correct |
1150 ms |
58652 KB |
Output is correct |
51 |
Correct |
1016 ms |
62388 KB |
Output is correct |