#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44
using namespace std;
const ll INF = 1e18;
vector < vector < pair <int, int> > > g;
vector <ll> dst[4];
int n;
inline void dijkstra(int nod, vector <ll> &dst) {
dst.resize(n + 1);
fill(dst.begin(), dst.end(), INF);
priority_queue < pair <ll, int> > pq;
pq.push({0, nod});
dst[nod] = 0;
vector <bool> vis(n + 1);
fill(vis.begin(), vis.end(), 0);
while(pq.size()) {
pair <ll, int> cur = pq.top();
pq.pop();
if(vis[cur.second]) {
continue;
}
vis[cur.second] = 1;
for(auto it : g[cur.second]) {
if(dst[it.first] > -cur.first + it.second) {
dst[it.first] = -cur.first + it.second;
pq.push({-dst[it.first], it.first});
}
}
}
}
vector <bool> vis;
vector <int> top;
void dfs(int nod, vector < vector <int> > &dag) {
vis[nod] = 1;
for(auto it : dag[nod]) {
if(vis[it] == 0) {
dfs(it, dag);
}
}
top.push_back(nod);
}
int main() {
//ifstream cin("A.in");
//ofstream cout("A.out");
int i, m, s, t, u, v;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
cin >> s >> t;
cin >> u >> v;
g.resize(n + 1);
for(i = 1; i <= m; i++) {
int x, y, c;
cin >> x >> y >> c;
g[x].push_back({y, c});
g[y].push_back({x, c});
}
vis.resize(n + 1);
ll ans = INF;
for(int p = 0; p < 2; p++) {
swap(u, v);
dijkstra(s, dst[0]); // s
dijkstra(t, dst[1]); // t
dijkstra(u, dst[2]); // u
dijkstra(v, dst[3]); // v
ans = min(ans, dst[2][v]);
vector < vector <int> > dag(n + 1);
for(i = 1; i <= n; i++) {
for(auto it : g[i]) {
if(dst[0][it.first] + it.second + dst[1][i] == dst[0][t]) {
dag[it.first].push_back(i);
}
}
}
fill(vis.begin(), vis.end(), 0);
top.clear();
for(i = 1; i <= n; i++) {
if(vis[i] == 0 && dst[0][i] + dst[1][i] == dst[0][t]) {
dfs(i, dag);
}
}
vector <ll> dp(n + 1, INF);
for(auto nod : top) {
dp[nod] = min(dp[nod], dst[3][nod]);
for(auto it : dag[nod]) {
dp[nod] = min(dp[nod], dp[it]);
}
ans = min(ans, dp[nod] + dst[2][nod]);
}
}
cout << ans;
//cin.close();
//cout.close();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
710 ms |
15536 KB |
Output is correct |
2 |
Correct |
802 ms |
19804 KB |
Output is correct |
3 |
Correct |
726 ms |
23360 KB |
Output is correct |
4 |
Correct |
757 ms |
20452 KB |
Output is correct |
5 |
Correct |
711 ms |
20544 KB |
Output is correct |
6 |
Correct |
716 ms |
19432 KB |
Output is correct |
7 |
Correct |
809 ms |
21068 KB |
Output is correct |
8 |
Correct |
798 ms |
20736 KB |
Output is correct |
9 |
Correct |
696 ms |
19884 KB |
Output is correct |
10 |
Correct |
594 ms |
19876 KB |
Output is correct |
11 |
Correct |
291 ms |
17980 KB |
Output is correct |
12 |
Correct |
590 ms |
19600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
719 ms |
17032 KB |
Output is correct |
2 |
Correct |
832 ms |
20872 KB |
Output is correct |
3 |
Correct |
825 ms |
21064 KB |
Output is correct |
4 |
Correct |
858 ms |
20272 KB |
Output is correct |
5 |
Correct |
888 ms |
20788 KB |
Output is correct |
6 |
Correct |
821 ms |
23136 KB |
Output is correct |
7 |
Correct |
902 ms |
24392 KB |
Output is correct |
8 |
Correct |
804 ms |
20672 KB |
Output is correct |
9 |
Correct |
791 ms |
21256 KB |
Output is correct |
10 |
Correct |
734 ms |
21156 KB |
Output is correct |
11 |
Correct |
315 ms |
19444 KB |
Output is correct |
12 |
Correct |
725 ms |
23840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
1024 KB |
Output is correct |
2 |
Correct |
3 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
25 ms |
2432 KB |
Output is correct |
5 |
Correct |
11 ms |
1356 KB |
Output is correct |
6 |
Correct |
3 ms |
384 KB |
Output is correct |
7 |
Correct |
4 ms |
512 KB |
Output is correct |
8 |
Correct |
4 ms |
512 KB |
Output is correct |
9 |
Correct |
4 ms |
512 KB |
Output is correct |
10 |
Correct |
11 ms |
1408 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
3 ms |
384 KB |
Output is correct |
14 |
Correct |
3 ms |
384 KB |
Output is correct |
15 |
Correct |
3 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
710 ms |
15536 KB |
Output is correct |
2 |
Correct |
802 ms |
19804 KB |
Output is correct |
3 |
Correct |
726 ms |
23360 KB |
Output is correct |
4 |
Correct |
757 ms |
20452 KB |
Output is correct |
5 |
Correct |
711 ms |
20544 KB |
Output is correct |
6 |
Correct |
716 ms |
19432 KB |
Output is correct |
7 |
Correct |
809 ms |
21068 KB |
Output is correct |
8 |
Correct |
798 ms |
20736 KB |
Output is correct |
9 |
Correct |
696 ms |
19884 KB |
Output is correct |
10 |
Correct |
594 ms |
19876 KB |
Output is correct |
11 |
Correct |
291 ms |
17980 KB |
Output is correct |
12 |
Correct |
590 ms |
19600 KB |
Output is correct |
13 |
Correct |
719 ms |
17032 KB |
Output is correct |
14 |
Correct |
832 ms |
20872 KB |
Output is correct |
15 |
Correct |
825 ms |
21064 KB |
Output is correct |
16 |
Correct |
858 ms |
20272 KB |
Output is correct |
17 |
Correct |
888 ms |
20788 KB |
Output is correct |
18 |
Correct |
821 ms |
23136 KB |
Output is correct |
19 |
Correct |
902 ms |
24392 KB |
Output is correct |
20 |
Correct |
804 ms |
20672 KB |
Output is correct |
21 |
Correct |
791 ms |
21256 KB |
Output is correct |
22 |
Correct |
734 ms |
21156 KB |
Output is correct |
23 |
Correct |
315 ms |
19444 KB |
Output is correct |
24 |
Correct |
725 ms |
23840 KB |
Output is correct |
25 |
Correct |
11 ms |
1024 KB |
Output is correct |
26 |
Correct |
3 ms |
384 KB |
Output is correct |
27 |
Correct |
2 ms |
384 KB |
Output is correct |
28 |
Correct |
25 ms |
2432 KB |
Output is correct |
29 |
Correct |
11 ms |
1356 KB |
Output is correct |
30 |
Correct |
3 ms |
384 KB |
Output is correct |
31 |
Correct |
4 ms |
512 KB |
Output is correct |
32 |
Correct |
4 ms |
512 KB |
Output is correct |
33 |
Correct |
4 ms |
512 KB |
Output is correct |
34 |
Correct |
11 ms |
1408 KB |
Output is correct |
35 |
Correct |
2 ms |
384 KB |
Output is correct |
36 |
Correct |
2 ms |
384 KB |
Output is correct |
37 |
Correct |
3 ms |
384 KB |
Output is correct |
38 |
Correct |
3 ms |
384 KB |
Output is correct |
39 |
Correct |
3 ms |
384 KB |
Output is correct |
40 |
Correct |
570 ms |
19644 KB |
Output is correct |
41 |
Correct |
587 ms |
19628 KB |
Output is correct |
42 |
Correct |
587 ms |
19688 KB |
Output is correct |
43 |
Correct |
281 ms |
20596 KB |
Output is correct |
44 |
Correct |
386 ms |
20848 KB |
Output is correct |
45 |
Correct |
778 ms |
22508 KB |
Output is correct |
46 |
Correct |
784 ms |
22284 KB |
Output is correct |
47 |
Correct |
663 ms |
20600 KB |
Output is correct |
48 |
Correct |
467 ms |
18544 KB |
Output is correct |
49 |
Correct |
612 ms |
19352 KB |
Output is correct |
50 |
Correct |
785 ms |
21800 KB |
Output is correct |
51 |
Correct |
799 ms |
22384 KB |
Output is correct |