#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
typedef long long ll;
typedef long double ldb;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<double> vdb;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;
typedef vector<string> vs;
typedef set<int> si;
typedef set<long long> sl;
typedef set<double> sdb;
typedef set<string> ss;
typedef set<char> sc;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ftb(i, a, b) for (int i = a, _b = b; i <= _b; ++i)
#define ft(i, a, b) for (int i = a, _b = b; i < _b; ++i)
#define fgb(i, a, b) for (int i = a, _b = b; i >= _b; --i)
#define fg(i, a, b) for (int i = a, _b = b; i > _b; --i)
#define endl "\n"
void dijkstra(int node, vector<pll> adj[], vl& distance) {
distance[node] = 0;
priority_queue<pll, vector<pll>, greater<pll>> q;
q.push({ 0,node });
while (!q.empty()) {
int node = q.top().second;
ll d = q.top().first;
q.pop();
if (d > distance[node]) continue;
for (pll it : adj[node]) {
if (distance[it.first] > d + it.second) {
distance[it.first] = d + it.second;
q.push({ d + it.second,it.first });
}
}
}
}
void dijkstra2(int node, vector<pll> adj[], vl parent[], int n) {
vl distance(n + 1, 1e17);
distance[node] = 0;
priority_queue<pll, vector<pll>, greater<pll>> q;
q.push({ 0,node });
while (!q.empty()) {
int node = q.top().second;
ll d = q.top().first;
q.pop();
if (d > distance[node]) continue;
for (pll it : adj[node]) {
if (distance[it.first] > d + it.second) {
distance[it.first] = d + it.second;
q.push({ d + it.second,it.first });
parent[it.first].clear();
parent[it.first].push_back(node);
}
else if (distance[it.first] == d + it.second) {
parent[it.first].push_back(node);
}
}
}
}
void bfs(int n, int s, vl adj[], vl& disU, vl& disV, ll& ans) {
vi cnt(n + 1, 0);
ftb(i, 1, n) {
for (int it : adj[i]) {
cnt[it] += 1;
}
}
queue<int> q;
vl mn(n + 1, 0);
ftb(i, 1, n) {
mn[i] = disU[i];
}
q.push(s);
while (!q.empty()) {
int node = q.front();
q.pop();
ans = min(ans, mn[node] + disV[node]);
for (int it : adj[node]) {
cnt[it] -= 1;
mn[it] = min(mn[it], mn[node]);
if (cnt[it] == 0) {
q.push(it);
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// freopen("C:\\Users\\tring\\Downloads\\2018-ho-data\\2018-ho-data\\2018-ho-t4\\in\\03-01.txt", "r", stdin);
ll n, m;
cin >> n >> m;
ll s, t, u, v;
cin >> s >> t >> u >> v;
vector<pll> adj[n + 1];
ft(i, 0, m) {
ll x, y, z;
cin >> x >> y >> z;
adj[x].push_back({ y,z });
adj[y].push_back({ x,z });
}
vl disU(n + 1, 1e17), disV(n + 1, 1e17);
dijkstra(u, adj, disU);
dijkstra(v, adj, disV);
vl parent[n + 1];
vl adj2[n + 1];
queue<int> q;
q.push(t);
vector<bool> check(n + 1, false);
dijkstra2(s, adj, parent, n);
while (!q.empty()) {
int node = q.front();
q.pop();
for (int it : parent[node]) {
if (!check[it]) {
check[it] = true;
q.push(it);
}
adj2[node].push_back(it);
}
}
ll ans = disU[v];
bfs(n, t, adj2, disU, disV, ans);
bfs(n, t, adj2, disV, disU, ans);
cout << ans << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
198 ms |
24548 KB |
Output is correct |
2 |
Correct |
183 ms |
24328 KB |
Output is correct |
3 |
Correct |
187 ms |
25112 KB |
Output is correct |
4 |
Correct |
200 ms |
24068 KB |
Output is correct |
5 |
Correct |
176 ms |
24892 KB |
Output is correct |
6 |
Correct |
179 ms |
23980 KB |
Output is correct |
7 |
Correct |
206 ms |
25204 KB |
Output is correct |
8 |
Correct |
201 ms |
24852 KB |
Output is correct |
9 |
Correct |
165 ms |
23448 KB |
Output is correct |
10 |
Correct |
155 ms |
23612 KB |
Output is correct |
11 |
Correct |
73 ms |
19520 KB |
Output is correct |
12 |
Correct |
182 ms |
23376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
189 ms |
24240 KB |
Output is correct |
2 |
Correct |
204 ms |
24204 KB |
Output is correct |
3 |
Correct |
194 ms |
24284 KB |
Output is correct |
4 |
Correct |
206 ms |
24480 KB |
Output is correct |
5 |
Correct |
197 ms |
24084 KB |
Output is correct |
6 |
Correct |
192 ms |
24796 KB |
Output is correct |
7 |
Correct |
210 ms |
25228 KB |
Output is correct |
8 |
Correct |
196 ms |
24244 KB |
Output is correct |
9 |
Correct |
200 ms |
24156 KB |
Output is correct |
10 |
Correct |
200 ms |
24204 KB |
Output is correct |
11 |
Correct |
75 ms |
20036 KB |
Output is correct |
12 |
Correct |
191 ms |
24828 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
1884 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
10 ms |
3164 KB |
Output is correct |
5 |
Correct |
8 ms |
1624 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
5 ms |
1628 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
198 ms |
24548 KB |
Output is correct |
2 |
Correct |
183 ms |
24328 KB |
Output is correct |
3 |
Correct |
187 ms |
25112 KB |
Output is correct |
4 |
Correct |
200 ms |
24068 KB |
Output is correct |
5 |
Correct |
176 ms |
24892 KB |
Output is correct |
6 |
Correct |
179 ms |
23980 KB |
Output is correct |
7 |
Correct |
206 ms |
25204 KB |
Output is correct |
8 |
Correct |
201 ms |
24852 KB |
Output is correct |
9 |
Correct |
165 ms |
23448 KB |
Output is correct |
10 |
Correct |
155 ms |
23612 KB |
Output is correct |
11 |
Correct |
73 ms |
19520 KB |
Output is correct |
12 |
Correct |
182 ms |
23376 KB |
Output is correct |
13 |
Correct |
189 ms |
24240 KB |
Output is correct |
14 |
Correct |
204 ms |
24204 KB |
Output is correct |
15 |
Correct |
194 ms |
24284 KB |
Output is correct |
16 |
Correct |
206 ms |
24480 KB |
Output is correct |
17 |
Correct |
197 ms |
24084 KB |
Output is correct |
18 |
Correct |
192 ms |
24796 KB |
Output is correct |
19 |
Correct |
210 ms |
25228 KB |
Output is correct |
20 |
Correct |
196 ms |
24244 KB |
Output is correct |
21 |
Correct |
200 ms |
24156 KB |
Output is correct |
22 |
Correct |
200 ms |
24204 KB |
Output is correct |
23 |
Correct |
75 ms |
20036 KB |
Output is correct |
24 |
Correct |
191 ms |
24828 KB |
Output is correct |
25 |
Correct |
6 ms |
1884 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
348 KB |
Output is correct |
28 |
Correct |
10 ms |
3164 KB |
Output is correct |
29 |
Correct |
8 ms |
1624 KB |
Output is correct |
30 |
Correct |
1 ms |
348 KB |
Output is correct |
31 |
Correct |
1 ms |
604 KB |
Output is correct |
32 |
Correct |
1 ms |
604 KB |
Output is correct |
33 |
Correct |
1 ms |
348 KB |
Output is correct |
34 |
Correct |
5 ms |
1628 KB |
Output is correct |
35 |
Correct |
0 ms |
344 KB |
Output is correct |
36 |
Correct |
0 ms |
348 KB |
Output is correct |
37 |
Correct |
0 ms |
348 KB |
Output is correct |
38 |
Correct |
1 ms |
348 KB |
Output is correct |
39 |
Correct |
1 ms |
348 KB |
Output is correct |
40 |
Correct |
170 ms |
23428 KB |
Output is correct |
41 |
Correct |
175 ms |
23400 KB |
Output is correct |
42 |
Correct |
187 ms |
23452 KB |
Output is correct |
43 |
Correct |
80 ms |
21324 KB |
Output is correct |
44 |
Correct |
79 ms |
21312 KB |
Output is correct |
45 |
Correct |
207 ms |
27048 KB |
Output is correct |
46 |
Correct |
189 ms |
27176 KB |
Output is correct |
47 |
Correct |
180 ms |
23872 KB |
Output is correct |
48 |
Correct |
80 ms |
21312 KB |
Output is correct |
49 |
Correct |
153 ms |
24332 KB |
Output is correct |
50 |
Correct |
186 ms |
26216 KB |
Output is correct |
51 |
Correct |
180 ms |
27184 KB |
Output is correct |