#pragma GCC optimize("Ofast,unroll-loops,shrink-wrap-separate,loop-nest-optimize,inline")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#include <bits/stdc++.h>
#include <tr1/unordered_map>
#include <tr1/unordered_set>
// #include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define IOS ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define mt make_tuple
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define mat vector<vector<ll>>
#define mat2 vector<vector<mat>>
#define vi vector<int>
#define vll vector<ll>
#define lll __int128_t
#define psi pair<string, int>
#define pis pair<int, string>
#define pic pair<int, char>
#define pcc pair<char, char>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define piiii pair<pii, pii>
#define mii map<int, int>
#define umii tr1::unordered_map<int, int>
#define iter set<int>::iterator
#define lb lower_bound
#define ub upper_bound
#define lg2(n) (31 - __builtin_clz(n))
#define lg2ll(n) (63 - __builtin_clzll(n))
#define fi first
#define se second
/*
#define fi first.first
#define se first.second
#define th second.first
#define fo second.second
*/
/*
#define piii pair<int, pii>
#define fi first
#define se second.fi
#define th second.second
*/
/*
#define piii pair<pii, int>
#define fi first.first
#define se first.th
#define th second
*/
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using namespace std;
// using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef tree<pll, null_type, greater<pll>, rb_tree_tag, tree_order_statistics_node_update> ost;
const int nax = 400005, block = 320, dax = 2, lim = 2187, lgax = 25, bit = 29, mod = 1000000007, inf = 1000000007;
const ll llax = 1e18;
const ld pi = acos(0) * 2;
const double eps = 1e-6;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
/*
const int MAX_MEM = 100000000;
int mpos;
char mem[MAX_MEM];
inline void* operator new(size_t n) {
assert((mpos += n) <= MAX_MEM);
return (void*)(mem + mpos - n);
}
inline void operator delete(void*) {}
*/
inline int read() {
char c = getchar_unlocked();
int t = 0, f = 1;
while (!isdigit(c) && c != EOF)
f = (c == '-' ? -1 : 1), c = getchar_unlocked();
while (isdigit(c) && c != EOF)
t = t * 10 + c - '0', c = getchar_unlocked();
return t * f;
}
inline void read(char* s) {
char c = getchar_unlocked();
while (isspace(c))
c = getchar_unlocked();
while (!isspace(c))
*s++ = c, c = getchar_unlocked();
*s = '\0';
}
/*
struct chash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
*/
int n, m;
ll d[2][nax], c[nax], dp[nax];
pii e[nax];
vector<pll> g[nax];
bitset<nax> vis;
void dijkstra(int s, int k) {
priority_queue<pll, vector<pll>, greater<pll>> q;
q.push({0, s});
fill(d[k], d[k] + nax, llax);
d[k][s] = 0;
while (!q.empty()) {
ll v = q.top().se, cur_d = q.top().fi;
q.pop();
if (cur_d > d[k][v])
continue;
for (pll ch : g[v])
if (d[k][ch.fi] > d[k][v] + max(c[ch.se], c[ch.se ^ 1]))
q.push({d[k][ch.fi] = d[k][v] + max(c[ch.se], c[ch.se ^ 1]), ch.fi});
}
}
ll dfs(int v) {
if (vis[v])
return dp[v];
vis[v] = 1;
for (pll ch : g[v])
if (!c[ch.se])
dp[v] = min(dp[v], dfs(ch.fi));
return dp[v];
}
int main() {
// IOS
ll ans = llax;
n = read(), m = read();
int s = read(), t = read(), x = read(), y = read();
for (int i = 0; i < 2 * m; ++i) {
int v = read(), u = read(), w = read();
g[v].eb(u, i), c[i] = w;
e[i] = {v, u};
++i;
g[u].eb(v, i), c[i] = w;
e[i] = {u, v};
}
dijkstra(x, 0);
ans = d[0][y];
dijkstra(s, 0);
dijkstra(t, 1);
for (int j = 0; j < 2 * m; ++j) {
if (d[0][e[j].fi] + c[j] + d[1][e[j].se] == d[0][t])
c[j] = 0;
}
dijkstra(x, 0);
dijkstra(y, 1);
for (int i = 1; i <= n; ++i)
dp[i] = d[1][i];
dfs(s);
for (int i = 1; i <= n; ++i)
ans = min(ans, d[0][i] + dp[i]);
vis = 0;
dijkstra(y, 0);
dijkstra(x, 1);
for (int i = 1; i <= n; ++i)
dp[i] = d[1][i];
dfs(s);
for (int i = 1; i <= n; ++i)
ans = min(ans, d[0][i] + dp[i]);
printf("%lld\n", ans);
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
566 ms |
36724 KB |
Output is correct |
2 |
Correct |
557 ms |
35672 KB |
Output is correct |
3 |
Correct |
621 ms |
39412 KB |
Output is correct |
4 |
Correct |
544 ms |
36724 KB |
Output is correct |
5 |
Correct |
560 ms |
35520 KB |
Output is correct |
6 |
Correct |
567 ms |
36908 KB |
Output is correct |
7 |
Correct |
562 ms |
35632 KB |
Output is correct |
8 |
Correct |
556 ms |
35868 KB |
Output is correct |
9 |
Correct |
549 ms |
35312 KB |
Output is correct |
10 |
Correct |
421 ms |
35180 KB |
Output is correct |
11 |
Correct |
221 ms |
28012 KB |
Output is correct |
12 |
Correct |
539 ms |
35352 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
579 ms |
37432 KB |
Output is correct |
2 |
Correct |
593 ms |
37716 KB |
Output is correct |
3 |
Correct |
599 ms |
37168 KB |
Output is correct |
4 |
Correct |
598 ms |
37484 KB |
Output is correct |
5 |
Correct |
591 ms |
37816 KB |
Output is correct |
6 |
Correct |
568 ms |
38968 KB |
Output is correct |
7 |
Correct |
625 ms |
39684 KB |
Output is correct |
8 |
Correct |
598 ms |
37620 KB |
Output is correct |
9 |
Correct |
593 ms |
38004 KB |
Output is correct |
10 |
Correct |
587 ms |
37332 KB |
Output is correct |
11 |
Correct |
243 ms |
29164 KB |
Output is correct |
12 |
Correct |
606 ms |
39412 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
18156 KB |
Output is correct |
2 |
Correct |
11 ms |
16108 KB |
Output is correct |
3 |
Correct |
12 ms |
16108 KB |
Output is correct |
4 |
Correct |
20 ms |
20332 KB |
Output is correct |
5 |
Correct |
17 ms |
18156 KB |
Output is correct |
6 |
Correct |
12 ms |
16236 KB |
Output is correct |
7 |
Correct |
12 ms |
16364 KB |
Output is correct |
8 |
Correct |
14 ms |
16492 KB |
Output is correct |
9 |
Correct |
13 ms |
16236 KB |
Output is correct |
10 |
Correct |
16 ms |
18540 KB |
Output is correct |
11 |
Correct |
11 ms |
16108 KB |
Output is correct |
12 |
Correct |
12 ms |
16108 KB |
Output is correct |
13 |
Correct |
12 ms |
16108 KB |
Output is correct |
14 |
Correct |
12 ms |
16236 KB |
Output is correct |
15 |
Correct |
11 ms |
16236 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
566 ms |
36724 KB |
Output is correct |
2 |
Correct |
557 ms |
35672 KB |
Output is correct |
3 |
Correct |
621 ms |
39412 KB |
Output is correct |
4 |
Correct |
544 ms |
36724 KB |
Output is correct |
5 |
Correct |
560 ms |
35520 KB |
Output is correct |
6 |
Correct |
567 ms |
36908 KB |
Output is correct |
7 |
Correct |
562 ms |
35632 KB |
Output is correct |
8 |
Correct |
556 ms |
35868 KB |
Output is correct |
9 |
Correct |
549 ms |
35312 KB |
Output is correct |
10 |
Correct |
421 ms |
35180 KB |
Output is correct |
11 |
Correct |
221 ms |
28012 KB |
Output is correct |
12 |
Correct |
539 ms |
35352 KB |
Output is correct |
13 |
Correct |
579 ms |
37432 KB |
Output is correct |
14 |
Correct |
593 ms |
37716 KB |
Output is correct |
15 |
Correct |
599 ms |
37168 KB |
Output is correct |
16 |
Correct |
598 ms |
37484 KB |
Output is correct |
17 |
Correct |
591 ms |
37816 KB |
Output is correct |
18 |
Correct |
568 ms |
38968 KB |
Output is correct |
19 |
Correct |
625 ms |
39684 KB |
Output is correct |
20 |
Correct |
598 ms |
37620 KB |
Output is correct |
21 |
Correct |
593 ms |
38004 KB |
Output is correct |
22 |
Correct |
587 ms |
37332 KB |
Output is correct |
23 |
Correct |
243 ms |
29164 KB |
Output is correct |
24 |
Correct |
606 ms |
39412 KB |
Output is correct |
25 |
Correct |
20 ms |
18156 KB |
Output is correct |
26 |
Correct |
11 ms |
16108 KB |
Output is correct |
27 |
Correct |
12 ms |
16108 KB |
Output is correct |
28 |
Correct |
20 ms |
20332 KB |
Output is correct |
29 |
Correct |
17 ms |
18156 KB |
Output is correct |
30 |
Correct |
12 ms |
16236 KB |
Output is correct |
31 |
Correct |
12 ms |
16364 KB |
Output is correct |
32 |
Correct |
14 ms |
16492 KB |
Output is correct |
33 |
Correct |
13 ms |
16236 KB |
Output is correct |
34 |
Correct |
16 ms |
18540 KB |
Output is correct |
35 |
Correct |
11 ms |
16108 KB |
Output is correct |
36 |
Correct |
12 ms |
16108 KB |
Output is correct |
37 |
Correct |
12 ms |
16108 KB |
Output is correct |
38 |
Correct |
12 ms |
16236 KB |
Output is correct |
39 |
Correct |
11 ms |
16236 KB |
Output is correct |
40 |
Correct |
504 ms |
40612 KB |
Output is correct |
41 |
Correct |
523 ms |
39752 KB |
Output is correct |
42 |
Correct |
532 ms |
39760 KB |
Output is correct |
43 |
Correct |
241 ms |
30444 KB |
Output is correct |
44 |
Correct |
242 ms |
30520 KB |
Output is correct |
45 |
Correct |
528 ms |
38540 KB |
Output is correct |
46 |
Correct |
530 ms |
38292 KB |
Output is correct |
47 |
Correct |
541 ms |
40324 KB |
Output is correct |
48 |
Correct |
278 ms |
27884 KB |
Output is correct |
49 |
Correct |
436 ms |
40204 KB |
Output is correct |
50 |
Correct |
530 ms |
38648 KB |
Output is correct |
51 |
Correct |
512 ms |
38696 KB |
Output is correct |