//by szh
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
const int maxn = 2e5+10;
int n,m,s,t,U,V;
vector <pii> edge[maxn];
ll dis[4][maxn];
pq <pll,vector<pll>,greater<pll> > q;
ll ans[maxn][2][2];
void dijkstra(int sta,int id) {
memset(dis[id],inf,sizeof(dis[id]));
dis[id][sta]=0;
q.push({0,sta});
while (!q.empty()) {
ll u = q.top().se,d=q.top().fi;
q.pop();
if (dis[id][u]!=d) continue;
for (pii v:edge[u]) {
if (dis[id][v.fi]>d+v.se) {
dis[id][v.fi]=d+v.se;
q.push({d+v.se,v.fi});
}
}
}
}
ll getdp(int u,int flag1,int flag2) {
if (u==t) return flag1*dis[2][u]+flag2*dis[3][u];
if (ans[u][flag1][flag2]!=-1) return ans[u][flag1][flag2];
ll ret = 1e16;
for (pii v:edge[u]) {
if (dis[1][v.fi]+v.se+dis[0][u]!=dis[0][t]) continue;
ret=min(ret,getdp(v.fi,flag1,flag2));
if (flag1==1) ret=min(ret,getdp(v.fi,0,flag2)+dis[2][u]);
if (flag2==1) ret=min(ret,getdp(v.fi,flag1,0)+dis[3][u]);
}
return ans[u][flag1][flag2]=ret;
}
int main() {
// freopen("input.txt","r",stdin);
std::ios::sync_with_stdio(false);cin.tie(0);
memset(ans,-1,sizeof(ans));
cin>>n>>m>>s>>t>>U>>V;
rep(i,0,m) {
int u,v,w;
cin>>u>>v>>w;
edge[u].pb({v,w});
edge[v].pb({u,w});
}
dijkstra(U,2);
dijkstra(s,0);
dijkstra(t,1);
dijkstra(V,3);
// debug(dis[2][V]);
cout<<min(dis[2][V],getdp(s,1,1));
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
250 ms |
24908 KB |
Output is correct |
2 |
Correct |
257 ms |
24928 KB |
Output is correct |
3 |
Correct |
312 ms |
32168 KB |
Output is correct |
4 |
Correct |
252 ms |
25920 KB |
Output is correct |
5 |
Correct |
334 ms |
24776 KB |
Output is correct |
6 |
Correct |
267 ms |
28920 KB |
Output is correct |
7 |
Correct |
290 ms |
28448 KB |
Output is correct |
8 |
Correct |
296 ms |
28588 KB |
Output is correct |
9 |
Correct |
236 ms |
28956 KB |
Output is correct |
10 |
Correct |
250 ms |
28988 KB |
Output is correct |
11 |
Correct |
158 ms |
27212 KB |
Output is correct |
12 |
Correct |
272 ms |
28916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
302 ms |
27940 KB |
Output is correct |
2 |
Correct |
290 ms |
28344 KB |
Output is correct |
3 |
Correct |
292 ms |
31104 KB |
Output is correct |
4 |
Correct |
326 ms |
31564 KB |
Output is correct |
5 |
Correct |
265 ms |
32356 KB |
Output is correct |
6 |
Correct |
295 ms |
35132 KB |
Output is correct |
7 |
Correct |
280 ms |
35400 KB |
Output is correct |
8 |
Correct |
315 ms |
31752 KB |
Output is correct |
9 |
Correct |
313 ms |
32464 KB |
Output is correct |
10 |
Correct |
282 ms |
31200 KB |
Output is correct |
11 |
Correct |
114 ms |
29488 KB |
Output is correct |
12 |
Correct |
288 ms |
35584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
18268 KB |
Output is correct |
2 |
Correct |
8 ms |
17492 KB |
Output is correct |
3 |
Correct |
9 ms |
17536 KB |
Output is correct |
4 |
Correct |
19 ms |
18900 KB |
Output is correct |
5 |
Correct |
17 ms |
18632 KB |
Output is correct |
6 |
Correct |
9 ms |
17560 KB |
Output is correct |
7 |
Correct |
9 ms |
17620 KB |
Output is correct |
8 |
Correct |
10 ms |
17620 KB |
Output is correct |
9 |
Correct |
8 ms |
17600 KB |
Output is correct |
10 |
Correct |
14 ms |
18608 KB |
Output is correct |
11 |
Correct |
8 ms |
17536 KB |
Output is correct |
12 |
Correct |
7 ms |
17560 KB |
Output is correct |
13 |
Correct |
9 ms |
17492 KB |
Output is correct |
14 |
Correct |
9 ms |
17572 KB |
Output is correct |
15 |
Correct |
9 ms |
17552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
250 ms |
24908 KB |
Output is correct |
2 |
Correct |
257 ms |
24928 KB |
Output is correct |
3 |
Correct |
312 ms |
32168 KB |
Output is correct |
4 |
Correct |
252 ms |
25920 KB |
Output is correct |
5 |
Correct |
334 ms |
24776 KB |
Output is correct |
6 |
Correct |
267 ms |
28920 KB |
Output is correct |
7 |
Correct |
290 ms |
28448 KB |
Output is correct |
8 |
Correct |
296 ms |
28588 KB |
Output is correct |
9 |
Correct |
236 ms |
28956 KB |
Output is correct |
10 |
Correct |
250 ms |
28988 KB |
Output is correct |
11 |
Correct |
158 ms |
27212 KB |
Output is correct |
12 |
Correct |
272 ms |
28916 KB |
Output is correct |
13 |
Correct |
302 ms |
27940 KB |
Output is correct |
14 |
Correct |
290 ms |
28344 KB |
Output is correct |
15 |
Correct |
292 ms |
31104 KB |
Output is correct |
16 |
Correct |
326 ms |
31564 KB |
Output is correct |
17 |
Correct |
265 ms |
32356 KB |
Output is correct |
18 |
Correct |
295 ms |
35132 KB |
Output is correct |
19 |
Correct |
280 ms |
35400 KB |
Output is correct |
20 |
Correct |
315 ms |
31752 KB |
Output is correct |
21 |
Correct |
313 ms |
32464 KB |
Output is correct |
22 |
Correct |
282 ms |
31200 KB |
Output is correct |
23 |
Correct |
114 ms |
29488 KB |
Output is correct |
24 |
Correct |
288 ms |
35584 KB |
Output is correct |
25 |
Correct |
14 ms |
18268 KB |
Output is correct |
26 |
Correct |
8 ms |
17492 KB |
Output is correct |
27 |
Correct |
9 ms |
17536 KB |
Output is correct |
28 |
Correct |
19 ms |
18900 KB |
Output is correct |
29 |
Correct |
17 ms |
18632 KB |
Output is correct |
30 |
Correct |
9 ms |
17560 KB |
Output is correct |
31 |
Correct |
9 ms |
17620 KB |
Output is correct |
32 |
Correct |
10 ms |
17620 KB |
Output is correct |
33 |
Correct |
8 ms |
17600 KB |
Output is correct |
34 |
Correct |
14 ms |
18608 KB |
Output is correct |
35 |
Correct |
8 ms |
17536 KB |
Output is correct |
36 |
Correct |
7 ms |
17560 KB |
Output is correct |
37 |
Correct |
9 ms |
17492 KB |
Output is correct |
38 |
Correct |
9 ms |
17572 KB |
Output is correct |
39 |
Correct |
9 ms |
17552 KB |
Output is correct |
40 |
Correct |
258 ms |
29248 KB |
Output is correct |
41 |
Correct |
262 ms |
28980 KB |
Output is correct |
42 |
Correct |
224 ms |
28992 KB |
Output is correct |
43 |
Correct |
184 ms |
28248 KB |
Output is correct |
44 |
Correct |
131 ms |
28236 KB |
Output is correct |
45 |
Correct |
257 ms |
27924 KB |
Output is correct |
46 |
Correct |
292 ms |
27676 KB |
Output is correct |
47 |
Correct |
253 ms |
28728 KB |
Output is correct |
48 |
Correct |
178 ms |
24160 KB |
Output is correct |
49 |
Correct |
225 ms |
28820 KB |
Output is correct |
50 |
Correct |
234 ms |
28100 KB |
Output is correct |
51 |
Correct |
261 ms |
27936 KB |
Output is correct |