#include <bits/stdc++.h>
#define MASK(i) (1LL << (i))
#define BIT(x, y) (((x) >> (y)) & 1)
#define sz(v) ((int) (v).size())
#define all(v) (v).begin(), (v).end()
#define uni(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define F first
#define S second
#define pii(x, y) make_pair(x, y)
#define __builtin_popcount __builtin_popcountll
#define __builtin_ctz __builtin_ctzll
#define __builtin_clz __builtin_clzll
#define lg(x) (63 - __builtin_clz(x))
template <class X, class Y>
bool minimize(X &x, const Y &y)
{
X eps = 1e-9;
if (x > y + eps) {x = y; return 1;}
return 0;
}
template <class X, class Y>
bool maximize(X &x, const Y &y)
{
X eps = 1e-9;
if (x + eps < y) {x = y; return 1;}
return 0;
}
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int M = 6e5;
const int mod = 1e9 + 7;
const int INF = 1e9 + 7;
const ll oo = 2e18;
const double eps = 1e-1;
const long double pi = 2*acos(0.0);
int n, m, s, t, U, V;
bool vs[N];
ll dp[4][N], f[N][2];
vector<pair<int, int>> ar[N];
void Input(void)
{
cin >> n >> m >> s >> t >> U >> V;
for (int i = 1; i <= m; i ++)
{
int u, v, w;
cin >> u >> v >> w;
ar[u].push_back(pii(v, w));
ar[v].push_back(pii(u, w));
}
}
void dijkstra(int idx, int source)
{
priority_queue<pair<ll, int>> st;
dp[idx][source] = 0;
st.push(pii(0, source));
while (sz(st))
{
auto [w, u] = st.top(); st.pop();
w = -w;
if (dp[idx][u] < w) continue;
for (auto [v, wi] : ar[u])
if (minimize(dp[idx][v], w + wi)) st.push(pii(- dp[idx][v], v));
}
}
ll ans = oo;
void bfs(int u)
{
f[u][0] = dp[2][u];
f[u][1] = dp[3][u];
priority_queue<pair<ll, int>> st;
st.push(pii(0, u));
vs[u] = 1;
while (sz(st))
{
auto [w, source] = st.top(); st.pop();
w = -w;
minimize(ans, f[source][1] + dp[2][source]);
minimize(ans, f[source][0] + dp[3][source]);
for (auto [sink, wi] : ar[source])
if (w + wi + dp[1][sink] == dp[0][t])
{
minimize(f[sink][0], min(f[source][0], dp[2][sink]));
minimize(f[sink][1], min(f[source][1], dp[3][sink]));
if (!vs[sink]) st.push(pii(- (w + wi), sink));
vs[sink] = 1;
}
}
}
void solve(void)
{
memset(dp, 0x3f, sizeof dp);
dijkstra(0, s);
dijkstra(1, t);
dijkstra(2, U);
dijkstra(3, V);
memset(f, 0x3f, sizeof f);
bfs(s);
cout << min(ans, dp[2][V]);
}
int main()
{
std::ios_base::sync_with_stdio(0); cin.tie(0);
int test = 1;
//cin >> test;
while (test --)
{
Input();
solve();
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
213 ms |
16896 KB |
Output is correct |
2 |
Correct |
175 ms |
15652 KB |
Output is correct |
3 |
Correct |
171 ms |
16732 KB |
Output is correct |
4 |
Correct |
158 ms |
16732 KB |
Output is correct |
5 |
Correct |
162 ms |
15452 KB |
Output is correct |
6 |
Correct |
186 ms |
17020 KB |
Output is correct |
7 |
Correct |
189 ms |
15656 KB |
Output is correct |
8 |
Correct |
182 ms |
15560 KB |
Output is correct |
9 |
Correct |
178 ms |
15472 KB |
Output is correct |
10 |
Correct |
136 ms |
15432 KB |
Output is correct |
11 |
Correct |
51 ms |
10584 KB |
Output is correct |
12 |
Correct |
189 ms |
15492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
187 ms |
15760 KB |
Output is correct |
2 |
Correct |
196 ms |
15672 KB |
Output is correct |
3 |
Correct |
177 ms |
15668 KB |
Output is correct |
4 |
Correct |
205 ms |
15960 KB |
Output is correct |
5 |
Correct |
190 ms |
15536 KB |
Output is correct |
6 |
Correct |
170 ms |
15588 KB |
Output is correct |
7 |
Correct |
223 ms |
15728 KB |
Output is correct |
8 |
Correct |
203 ms |
15536 KB |
Output is correct |
9 |
Correct |
193 ms |
15640 KB |
Output is correct |
10 |
Correct |
216 ms |
15744 KB |
Output is correct |
11 |
Correct |
54 ms |
10628 KB |
Output is correct |
12 |
Correct |
169 ms |
15712 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
8024 KB |
Output is correct |
2 |
Correct |
2 ms |
7512 KB |
Output is correct |
3 |
Correct |
2 ms |
7516 KB |
Output is correct |
4 |
Correct |
11 ms |
8884 KB |
Output is correct |
5 |
Correct |
6 ms |
8164 KB |
Output is correct |
6 |
Correct |
3 ms |
7768 KB |
Output is correct |
7 |
Correct |
2 ms |
7516 KB |
Output is correct |
8 |
Correct |
3 ms |
7768 KB |
Output is correct |
9 |
Correct |
2 ms |
7516 KB |
Output is correct |
10 |
Correct |
10 ms |
8792 KB |
Output is correct |
11 |
Correct |
2 ms |
7516 KB |
Output is correct |
12 |
Correct |
2 ms |
7516 KB |
Output is correct |
13 |
Correct |
2 ms |
7516 KB |
Output is correct |
14 |
Correct |
2 ms |
7516 KB |
Output is correct |
15 |
Correct |
2 ms |
7516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
213 ms |
16896 KB |
Output is correct |
2 |
Correct |
175 ms |
15652 KB |
Output is correct |
3 |
Correct |
171 ms |
16732 KB |
Output is correct |
4 |
Correct |
158 ms |
16732 KB |
Output is correct |
5 |
Correct |
162 ms |
15452 KB |
Output is correct |
6 |
Correct |
186 ms |
17020 KB |
Output is correct |
7 |
Correct |
189 ms |
15656 KB |
Output is correct |
8 |
Correct |
182 ms |
15560 KB |
Output is correct |
9 |
Correct |
178 ms |
15472 KB |
Output is correct |
10 |
Correct |
136 ms |
15432 KB |
Output is correct |
11 |
Correct |
51 ms |
10584 KB |
Output is correct |
12 |
Correct |
189 ms |
15492 KB |
Output is correct |
13 |
Correct |
187 ms |
15760 KB |
Output is correct |
14 |
Correct |
196 ms |
15672 KB |
Output is correct |
15 |
Correct |
177 ms |
15668 KB |
Output is correct |
16 |
Correct |
205 ms |
15960 KB |
Output is correct |
17 |
Correct |
190 ms |
15536 KB |
Output is correct |
18 |
Correct |
170 ms |
15588 KB |
Output is correct |
19 |
Correct |
223 ms |
15728 KB |
Output is correct |
20 |
Correct |
203 ms |
15536 KB |
Output is correct |
21 |
Correct |
193 ms |
15640 KB |
Output is correct |
22 |
Correct |
216 ms |
15744 KB |
Output is correct |
23 |
Correct |
54 ms |
10628 KB |
Output is correct |
24 |
Correct |
169 ms |
15712 KB |
Output is correct |
25 |
Correct |
6 ms |
8024 KB |
Output is correct |
26 |
Correct |
2 ms |
7512 KB |
Output is correct |
27 |
Correct |
2 ms |
7516 KB |
Output is correct |
28 |
Correct |
11 ms |
8884 KB |
Output is correct |
29 |
Correct |
6 ms |
8164 KB |
Output is correct |
30 |
Correct |
3 ms |
7768 KB |
Output is correct |
31 |
Correct |
2 ms |
7516 KB |
Output is correct |
32 |
Correct |
3 ms |
7768 KB |
Output is correct |
33 |
Correct |
2 ms |
7516 KB |
Output is correct |
34 |
Correct |
10 ms |
8792 KB |
Output is correct |
35 |
Correct |
2 ms |
7516 KB |
Output is correct |
36 |
Correct |
2 ms |
7516 KB |
Output is correct |
37 |
Correct |
2 ms |
7516 KB |
Output is correct |
38 |
Correct |
2 ms |
7516 KB |
Output is correct |
39 |
Correct |
2 ms |
7516 KB |
Output is correct |
40 |
Correct |
170 ms |
21176 KB |
Output is correct |
41 |
Correct |
184 ms |
19824 KB |
Output is correct |
42 |
Correct |
163 ms |
19860 KB |
Output is correct |
43 |
Correct |
52 ms |
12832 KB |
Output is correct |
44 |
Correct |
55 ms |
12624 KB |
Output is correct |
45 |
Correct |
166 ms |
18740 KB |
Output is correct |
46 |
Correct |
159 ms |
18516 KB |
Output is correct |
47 |
Correct |
167 ms |
20456 KB |
Output is correct |
48 |
Correct |
74 ms |
12228 KB |
Output is correct |
49 |
Correct |
139 ms |
20772 KB |
Output is correct |
50 |
Correct |
161 ms |
18860 KB |
Output is correct |
51 |
Correct |
165 ms |
18888 KB |
Output is correct |