#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define maxn 220000
int n, m, d[maxn];
int ds[maxn], dt[maxn], du[maxn], dv[maxn];
pair<int,int> d1[maxn];
vector<pair<int,int>> g[maxn];
void sph(int beg) {
for(int i = 1; i <= n; i++) {
d[i] = inf;
}
d[beg] = 0;
priority_queue<pair<int,int>> pq; pq.push(mp(0,beg));
while(pq.size()) {
int u = pq.top().sc;
int dist = -pq.top().fr;
pq.pop();
if(dist != d[u]) continue;
for(auto V : g[u]) {
int v = V.fr;
int w = V.sc;
if(d[v] > d[u]+w) {
d[v] = d[u]+w;
pq.push(mp(-d[v],v));
}
}
}
}
void sph1(int beg) {
for(int i = 1; i <= n; i++) {
d[i] = inf;
d1[i] = mp(du[i],dv[i]);
}
d[beg] = 0;
priority_queue<pair<int,int>> pq; pq.push(mp(0,beg));
while(pq.size()) {
int u = pq.top().sc;
int dist = -pq.top().fr;
pq.pop();
if(dist != d[u]) continue;
for(auto V : g[u]) {
int v = V.fr;
int w = V.sc;
if(d[v] > d[u]+w) {
d[v] = d[u]+w;
d1[v].fr = min(d1[u].fr,du[v]);
d1[v].sc = min(d1[u].sc,dv[v]);
pq.push(mp(-d[v],v));
}
else if(d[v] == d[u]+w) {
d1[v].fr = min(d1[u].fr,d1[v].fr);
d1[v].sc = min(d1[u].sc,d1[v].sc);
}
}
}
}
void solve() {
int S, T, U, V;
cin >> n >> m >> S >> T >> U >> V;
for(int i = 0; i < m; i++) {
int a,b,c;
cin >> a >> b >> c;
g[a].pb(mp(b,c));
g[b].pb(mp(a,c));
}
sph(U);
for(int i = 1; i <= n; i++) {
du[i] = d[i];
}
sph(V);
for(int i = 1; i <= n; i++) {
dv[i] = d[i];
}
sph(S);
for(int i = 1; i <= n; i++) {
ds[i] = d[i];
}
sph(T);
for(int i = 1; i <= n; i++) {
dt[i] = d[i];
}
sph1(S);
int ans = du[V];
for(int u = 1; u <= n; u++) {
for(auto V : g[u]) {
int v = V.fr;
int w = V.sc;
if(ds[u] + w + dt[v] == ds[T] || dt[u] + w + ds[v] == dt[S]) {
ans = min(ans, d1[u].fr + dv[u]);
ans = min(ans, du[u] + d1[u].sc);
}
}
}
cout << ans << endl;
}
int32_t main() {
ios::sync_with_stdio(false); cin.tie(0);
// freopen("in.in", "r", stdin);
//freopen("out.out", "w", stdout);
int tt = 1;
// cin >> tt;
while(tt--) solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
326 ms |
28448 KB |
Output is correct |
2 |
Correct |
303 ms |
26824 KB |
Output is correct |
3 |
Correct |
310 ms |
26696 KB |
Output is correct |
4 |
Correct |
322 ms |
27104 KB |
Output is correct |
5 |
Correct |
313 ms |
26420 KB |
Output is correct |
6 |
Correct |
332 ms |
28308 KB |
Output is correct |
7 |
Correct |
310 ms |
26688 KB |
Output is correct |
8 |
Correct |
327 ms |
26800 KB |
Output is correct |
9 |
Correct |
315 ms |
27584 KB |
Output is correct |
10 |
Correct |
268 ms |
27532 KB |
Output is correct |
11 |
Correct |
119 ms |
18132 KB |
Output is correct |
12 |
Correct |
373 ms |
27352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
322 ms |
27112 KB |
Output is correct |
2 |
Correct |
370 ms |
26808 KB |
Output is correct |
3 |
Correct |
361 ms |
26724 KB |
Output is correct |
4 |
Correct |
328 ms |
26764 KB |
Output is correct |
5 |
Correct |
364 ms |
26736 KB |
Output is correct |
6 |
Correct |
306 ms |
26700 KB |
Output is correct |
7 |
Correct |
325 ms |
26564 KB |
Output is correct |
8 |
Correct |
335 ms |
26676 KB |
Output is correct |
9 |
Correct |
373 ms |
26788 KB |
Output is correct |
10 |
Correct |
326 ms |
26720 KB |
Output is correct |
11 |
Correct |
125 ms |
18180 KB |
Output is correct |
12 |
Correct |
326 ms |
26820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
7236 KB |
Output is correct |
2 |
Correct |
3 ms |
5480 KB |
Output is correct |
3 |
Correct |
3 ms |
5484 KB |
Output is correct |
4 |
Correct |
16 ms |
9060 KB |
Output is correct |
5 |
Correct |
10 ms |
7288 KB |
Output is correct |
6 |
Correct |
4 ms |
5660 KB |
Output is correct |
7 |
Correct |
4 ms |
5628 KB |
Output is correct |
8 |
Correct |
4 ms |
5708 KB |
Output is correct |
9 |
Correct |
4 ms |
5752 KB |
Output is correct |
10 |
Correct |
9 ms |
7280 KB |
Output is correct |
11 |
Correct |
3 ms |
5488 KB |
Output is correct |
12 |
Correct |
3 ms |
5452 KB |
Output is correct |
13 |
Correct |
3 ms |
5536 KB |
Output is correct |
14 |
Correct |
3 ms |
5580 KB |
Output is correct |
15 |
Correct |
3 ms |
5580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
326 ms |
28448 KB |
Output is correct |
2 |
Correct |
303 ms |
26824 KB |
Output is correct |
3 |
Correct |
310 ms |
26696 KB |
Output is correct |
4 |
Correct |
322 ms |
27104 KB |
Output is correct |
5 |
Correct |
313 ms |
26420 KB |
Output is correct |
6 |
Correct |
332 ms |
28308 KB |
Output is correct |
7 |
Correct |
310 ms |
26688 KB |
Output is correct |
8 |
Correct |
327 ms |
26800 KB |
Output is correct |
9 |
Correct |
315 ms |
27584 KB |
Output is correct |
10 |
Correct |
268 ms |
27532 KB |
Output is correct |
11 |
Correct |
119 ms |
18132 KB |
Output is correct |
12 |
Correct |
373 ms |
27352 KB |
Output is correct |
13 |
Correct |
322 ms |
27112 KB |
Output is correct |
14 |
Correct |
370 ms |
26808 KB |
Output is correct |
15 |
Correct |
361 ms |
26724 KB |
Output is correct |
16 |
Correct |
328 ms |
26764 KB |
Output is correct |
17 |
Correct |
364 ms |
26736 KB |
Output is correct |
18 |
Correct |
306 ms |
26700 KB |
Output is correct |
19 |
Correct |
325 ms |
26564 KB |
Output is correct |
20 |
Correct |
335 ms |
26676 KB |
Output is correct |
21 |
Correct |
373 ms |
26788 KB |
Output is correct |
22 |
Correct |
326 ms |
26720 KB |
Output is correct |
23 |
Correct |
125 ms |
18180 KB |
Output is correct |
24 |
Correct |
326 ms |
26820 KB |
Output is correct |
25 |
Correct |
10 ms |
7236 KB |
Output is correct |
26 |
Correct |
3 ms |
5480 KB |
Output is correct |
27 |
Correct |
3 ms |
5484 KB |
Output is correct |
28 |
Correct |
16 ms |
9060 KB |
Output is correct |
29 |
Correct |
10 ms |
7288 KB |
Output is correct |
30 |
Correct |
4 ms |
5660 KB |
Output is correct |
31 |
Correct |
4 ms |
5628 KB |
Output is correct |
32 |
Correct |
4 ms |
5708 KB |
Output is correct |
33 |
Correct |
4 ms |
5752 KB |
Output is correct |
34 |
Correct |
9 ms |
7280 KB |
Output is correct |
35 |
Correct |
3 ms |
5488 KB |
Output is correct |
36 |
Correct |
3 ms |
5452 KB |
Output is correct |
37 |
Correct |
3 ms |
5536 KB |
Output is correct |
38 |
Correct |
3 ms |
5580 KB |
Output is correct |
39 |
Correct |
3 ms |
5580 KB |
Output is correct |
40 |
Correct |
300 ms |
28252 KB |
Output is correct |
41 |
Correct |
299 ms |
27416 KB |
Output is correct |
42 |
Correct |
307 ms |
27524 KB |
Output is correct |
43 |
Correct |
109 ms |
18244 KB |
Output is correct |
44 |
Correct |
118 ms |
18420 KB |
Output is correct |
45 |
Correct |
290 ms |
26308 KB |
Output is correct |
46 |
Correct |
294 ms |
26028 KB |
Output is correct |
47 |
Correct |
301 ms |
26864 KB |
Output is correct |
48 |
Correct |
120 ms |
17656 KB |
Output is correct |
49 |
Correct |
244 ms |
27964 KB |
Output is correct |
50 |
Correct |
293 ms |
26364 KB |
Output is correct |
51 |
Correct |
276 ms |
26312 KB |
Output is correct |