#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
#define int ll
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = (int)(1e6) + 5;
ll D1[N];
ll D2[N];
ll D3[N];
ll D4[N];
vector < pii > g[N];
int n;
void Go(ll D[],int S) {
for (int i = 1;i <= n;++i)
D[i] = 1e18;
D[S] = 0;
priority_queue < pair < ll , int > , vector < pair < ll , int > > , greater < pair < ll , int > > > Q;
Q.push(mp(0,S));
while (!Q.empty()) {
const ll cost = Q.top().fi;
const int node = Q.top().se;
Q.pop();
if (cost != D[node])
continue;
for (auto it : g[node])
if (D[it.fi] > D[node] + it.se)
D[it.fi] = D[node] + it.se,Q.push(mp(D[it.fi],it.fi));
}
}
ll ans = 1e18;
vi G[2][N];
int was[N];
void go(ll d1[],ll d2[],int who,vi order) {
static ll D[N];
for (int i = 1;i <= n;++i)
D[i] = d1[i];
for (auto u : order)
for (auto v : G[who][u])
smin(D[u],D[v]);
for (int i = 1;i <= n;++i)
smin(ans,D[i] + d2[i]);
}
ll dist;
void Sort(ll d1[],ll d2[],int st,vi &order,int who) {
for (int i = 1;i <= n;++i)
was[i] = 0;
queue < int > q;
q.push(st);
was[st] = 1;
while (!q.empty()) {
int node = q.front();
q.pop();
order.pb(node);
for (auto it : g[node])
if (d1[node] + it.se + d2[it.fi] == dist) {
G[who][node].pb(it.fi);
G[who^1][it.fi].pb(node);
if (!was[it.fi])
was[it.fi] = 1,q.push(it.fi);
}
}
}
int32_t main(void)
{
int m;
int S,T,U,V;
cin>>n>>m>>S>>T>>U>>V;
while (m --) {
int a,b,c;
cin>>a>>b>>c;
g[a].pb(mp(b,c));
g[b].pb(mp(a,c));
}
Go(D1,S);
Go(D2,T);
Go(D3,U);
Go(D4,V);
dist = D1[T];
vi order1,order2;
Sort(D1,D2,S,order1,0);
// Sort(D2,D1,T,order2,1);
order2 = order1;
reverse(all(order2));
ans = D3[V];
go(D3,D4,1,order1);
go(D4,D3,1,order1);
go(D3,D4,0,order2);
go(D4,D3,0,order2);
cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
633 ms |
87520 KB |
Output is correct |
2 |
Correct |
734 ms |
88096 KB |
Output is correct |
3 |
Correct |
773 ms |
91664 KB |
Output is correct |
4 |
Correct |
662 ms |
91664 KB |
Output is correct |
5 |
Correct |
661 ms |
91664 KB |
Output is correct |
6 |
Correct |
656 ms |
91664 KB |
Output is correct |
7 |
Correct |
723 ms |
91664 KB |
Output is correct |
8 |
Correct |
679 ms |
91664 KB |
Output is correct |
9 |
Correct |
651 ms |
91664 KB |
Output is correct |
10 |
Correct |
591 ms |
91664 KB |
Output is correct |
11 |
Correct |
372 ms |
91664 KB |
Output is correct |
12 |
Correct |
717 ms |
91664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
688 ms |
91664 KB |
Output is correct |
2 |
Correct |
692 ms |
91664 KB |
Output is correct |
3 |
Correct |
718 ms |
91664 KB |
Output is correct |
4 |
Correct |
731 ms |
91664 KB |
Output is correct |
5 |
Correct |
691 ms |
91664 KB |
Output is correct |
6 |
Correct |
707 ms |
91664 KB |
Output is correct |
7 |
Correct |
733 ms |
91672 KB |
Output is correct |
8 |
Correct |
697 ms |
91672 KB |
Output is correct |
9 |
Correct |
690 ms |
91672 KB |
Output is correct |
10 |
Correct |
698 ms |
91672 KB |
Output is correct |
11 |
Correct |
378 ms |
91672 KB |
Output is correct |
12 |
Correct |
821 ms |
91672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
87 ms |
91672 KB |
Output is correct |
2 |
Correct |
61 ms |
91672 KB |
Output is correct |
3 |
Correct |
59 ms |
91672 KB |
Output is correct |
4 |
Correct |
111 ms |
91672 KB |
Output is correct |
5 |
Correct |
86 ms |
91672 KB |
Output is correct |
6 |
Correct |
60 ms |
91672 KB |
Output is correct |
7 |
Incorrect |
65 ms |
91672 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
633 ms |
87520 KB |
Output is correct |
2 |
Correct |
734 ms |
88096 KB |
Output is correct |
3 |
Correct |
773 ms |
91664 KB |
Output is correct |
4 |
Correct |
662 ms |
91664 KB |
Output is correct |
5 |
Correct |
661 ms |
91664 KB |
Output is correct |
6 |
Correct |
656 ms |
91664 KB |
Output is correct |
7 |
Correct |
723 ms |
91664 KB |
Output is correct |
8 |
Correct |
679 ms |
91664 KB |
Output is correct |
9 |
Correct |
651 ms |
91664 KB |
Output is correct |
10 |
Correct |
591 ms |
91664 KB |
Output is correct |
11 |
Correct |
372 ms |
91664 KB |
Output is correct |
12 |
Correct |
717 ms |
91664 KB |
Output is correct |
13 |
Correct |
688 ms |
91664 KB |
Output is correct |
14 |
Correct |
692 ms |
91664 KB |
Output is correct |
15 |
Correct |
718 ms |
91664 KB |
Output is correct |
16 |
Correct |
731 ms |
91664 KB |
Output is correct |
17 |
Correct |
691 ms |
91664 KB |
Output is correct |
18 |
Correct |
707 ms |
91664 KB |
Output is correct |
19 |
Correct |
733 ms |
91672 KB |
Output is correct |
20 |
Correct |
697 ms |
91672 KB |
Output is correct |
21 |
Correct |
690 ms |
91672 KB |
Output is correct |
22 |
Correct |
698 ms |
91672 KB |
Output is correct |
23 |
Correct |
378 ms |
91672 KB |
Output is correct |
24 |
Correct |
821 ms |
91672 KB |
Output is correct |
25 |
Correct |
87 ms |
91672 KB |
Output is correct |
26 |
Correct |
61 ms |
91672 KB |
Output is correct |
27 |
Correct |
59 ms |
91672 KB |
Output is correct |
28 |
Correct |
111 ms |
91672 KB |
Output is correct |
29 |
Correct |
86 ms |
91672 KB |
Output is correct |
30 |
Correct |
60 ms |
91672 KB |
Output is correct |
31 |
Incorrect |
65 ms |
91672 KB |
Output isn't correct |
32 |
Halted |
0 ms |
0 KB |
- |