#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=3e5;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,d[4][maxN];
bool vis[maxN];
vector<pli>g[maxN],adj[maxN],ke[maxN];
void dij(ll s,ll t)
{
for(int i=1;i<=n;i++) d[t][i]=inf,vis[i]=false;
d[t][s]=0;
priority_queue<pli,vector<pli>,greater<pli>>pq;
pq.push({d[t][s],s});
while(!pq.empty())
{
ll u=pq.top().se;
pq.pop();
if(vis[u]==true) continue;
vis[u]=true;
for(auto vv:g[u])
{
ll v=vv.fi;
ll w=vv.se;
if(d[t][v]>d[t][u]+w)
{
d[t][v]=d[t][u]+w;
pq.push({d[t][v],v});
}
}
}
}
ll m,s,t,x,y;
struct qq
{
ll u,v,w;
}a[maxN];
ll deg[maxN];
vector<ll>rev[maxN];ll dp1[maxN],dp2[maxN];
ll ans=inf;
void cal()
{
for(int i=1;i<=n;i++) deg[i]=0,rev[i].clear(),dp1[i]=inf,dp2[i]=inf;
for(int i=1;i<=n;i++)
{
for(auto zz:g[i])
{
deg[zz.fi]++;
rev[zz.fi].pb(i);
}
}
queue<int>q;
for(int i=1;i<=n;i++) if(deg[i]==0) q.push(i);
vector<ll> ver;
while(!q.empty())
{
ll u=q.front();
q.pop();
ver.pb(u);
for(auto zz:g[u])
{
deg[zz.fi]--;
if(deg[zz.fi]==0) q.push(zz.fi);
}
}
for(auto zz:ver)
{
dp1[zz]=d[2][zz];
for(auto vv:rev[zz])
{
dp1[zz]=min(dp1[zz],dp1[vv]);
}
dp2[zz]=d[3][zz];
for(auto vv:rev[zz])
{
dp2[zz]=min(dp2[zz],dp2[vv]);
}
ans=min(ans,dp1[zz]+d[3][zz]);
ans=min(ans,dp2[zz]+d[2][zz]);
}
}
void solve()
{
cin >> n >> m;
cin >> s >> t;
cin >> x >> y;
for(int i=1;i<=m;i++)
{
ll u,v,w;
cin >> u >> v >> w;
a[i].u=u;
a[i].v=v;
a[i].w=w;
g[u].pb({v,w});
g[v].pb({u,w});
}
dij(s,0);
dij(t,1);
for(int i=1;i<=m;i++)
{
if(d[0][a[i].u]+d[1][a[i].v]+a[i].w==d[0][t])
{
adj[a[i].u].pb({a[i].v,0});
}
else if(d[0][a[i].v]+d[1][a[i].u]+a[i].w==d[0][t])
{
adj[a[i].v].pb({a[i].u,0});
}
}
for(int i=1;i<=m;i++)
{
if(d[0][a[i].u]+d[1][a[i].v]+a[i].w==d[0][t])
{
ke[a[i].v].pb({a[i].u,0});
}
else if(d[0][a[i].v]+d[1][a[i].u]+a[i].w==d[0][t])
{
ke[a[i].u].pb({a[i].v,0});
}
}
dij(x,2);
dij(y,3);
for(int i=1;i<=n;i++) swap(adj[i],g[i]);
cal();
for(int i=1;i<=n;i++) swap(ke[i],g[i]);
cal();
cout << ans;
}
int main()
{
fastio
//freopen(TASKNAME".INP","r",stdin);
//freopen(TASKNAME".OUT","w",stdout);
solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
294 ms |
52536 KB |
Output is correct |
2 |
Correct |
309 ms |
54552 KB |
Output is correct |
3 |
Correct |
321 ms |
57708 KB |
Output is correct |
4 |
Correct |
279 ms |
52352 KB |
Output is correct |
5 |
Correct |
331 ms |
57012 KB |
Output is correct |
6 |
Correct |
325 ms |
52300 KB |
Output is correct |
7 |
Correct |
355 ms |
57608 KB |
Output is correct |
8 |
Correct |
388 ms |
56788 KB |
Output is correct |
9 |
Correct |
310 ms |
52448 KB |
Output is correct |
10 |
Correct |
251 ms |
51840 KB |
Output is correct |
11 |
Correct |
159 ms |
47904 KB |
Output is correct |
12 |
Correct |
305 ms |
51848 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
318 ms |
54148 KB |
Output is correct |
2 |
Correct |
360 ms |
54620 KB |
Output is correct |
3 |
Correct |
388 ms |
54084 KB |
Output is correct |
4 |
Correct |
361 ms |
54644 KB |
Output is correct |
5 |
Correct |
400 ms |
55484 KB |
Output is correct |
6 |
Correct |
449 ms |
57456 KB |
Output is correct |
7 |
Correct |
413 ms |
58084 KB |
Output is correct |
8 |
Correct |
390 ms |
55172 KB |
Output is correct |
9 |
Correct |
362 ms |
55420 KB |
Output is correct |
10 |
Correct |
327 ms |
54592 KB |
Output is correct |
11 |
Correct |
172 ms |
50616 KB |
Output is correct |
12 |
Correct |
330 ms |
57808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
31308 KB |
Output is correct |
2 |
Correct |
15 ms |
28648 KB |
Output is correct |
3 |
Correct |
15 ms |
28532 KB |
Output is correct |
4 |
Correct |
30 ms |
33116 KB |
Output is correct |
5 |
Correct |
22 ms |
30796 KB |
Output is correct |
6 |
Correct |
16 ms |
28628 KB |
Output is correct |
7 |
Correct |
17 ms |
28796 KB |
Output is correct |
8 |
Correct |
17 ms |
28884 KB |
Output is correct |
9 |
Correct |
17 ms |
28728 KB |
Output is correct |
10 |
Correct |
21 ms |
30804 KB |
Output is correct |
11 |
Correct |
16 ms |
28628 KB |
Output is correct |
12 |
Correct |
16 ms |
28500 KB |
Output is correct |
13 |
Correct |
16 ms |
28628 KB |
Output is correct |
14 |
Correct |
16 ms |
28756 KB |
Output is correct |
15 |
Correct |
16 ms |
28664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
294 ms |
52536 KB |
Output is correct |
2 |
Correct |
309 ms |
54552 KB |
Output is correct |
3 |
Correct |
321 ms |
57708 KB |
Output is correct |
4 |
Correct |
279 ms |
52352 KB |
Output is correct |
5 |
Correct |
331 ms |
57012 KB |
Output is correct |
6 |
Correct |
325 ms |
52300 KB |
Output is correct |
7 |
Correct |
355 ms |
57608 KB |
Output is correct |
8 |
Correct |
388 ms |
56788 KB |
Output is correct |
9 |
Correct |
310 ms |
52448 KB |
Output is correct |
10 |
Correct |
251 ms |
51840 KB |
Output is correct |
11 |
Correct |
159 ms |
47904 KB |
Output is correct |
12 |
Correct |
305 ms |
51848 KB |
Output is correct |
13 |
Correct |
318 ms |
54148 KB |
Output is correct |
14 |
Correct |
360 ms |
54620 KB |
Output is correct |
15 |
Correct |
388 ms |
54084 KB |
Output is correct |
16 |
Correct |
361 ms |
54644 KB |
Output is correct |
17 |
Correct |
400 ms |
55484 KB |
Output is correct |
18 |
Correct |
449 ms |
57456 KB |
Output is correct |
19 |
Correct |
413 ms |
58084 KB |
Output is correct |
20 |
Correct |
390 ms |
55172 KB |
Output is correct |
21 |
Correct |
362 ms |
55420 KB |
Output is correct |
22 |
Correct |
327 ms |
54592 KB |
Output is correct |
23 |
Correct |
172 ms |
50616 KB |
Output is correct |
24 |
Correct |
330 ms |
57808 KB |
Output is correct |
25 |
Correct |
24 ms |
31308 KB |
Output is correct |
26 |
Correct |
15 ms |
28648 KB |
Output is correct |
27 |
Correct |
15 ms |
28532 KB |
Output is correct |
28 |
Correct |
30 ms |
33116 KB |
Output is correct |
29 |
Correct |
22 ms |
30796 KB |
Output is correct |
30 |
Correct |
16 ms |
28628 KB |
Output is correct |
31 |
Correct |
17 ms |
28796 KB |
Output is correct |
32 |
Correct |
17 ms |
28884 KB |
Output is correct |
33 |
Correct |
17 ms |
28728 KB |
Output is correct |
34 |
Correct |
21 ms |
30804 KB |
Output is correct |
35 |
Correct |
16 ms |
28628 KB |
Output is correct |
36 |
Correct |
16 ms |
28500 KB |
Output is correct |
37 |
Correct |
16 ms |
28628 KB |
Output is correct |
38 |
Correct |
16 ms |
28756 KB |
Output is correct |
39 |
Correct |
16 ms |
28664 KB |
Output is correct |
40 |
Correct |
293 ms |
54696 KB |
Output is correct |
41 |
Correct |
320 ms |
55636 KB |
Output is correct |
42 |
Correct |
332 ms |
55644 KB |
Output is correct |
43 |
Correct |
253 ms |
54588 KB |
Output is correct |
44 |
Correct |
191 ms |
54648 KB |
Output is correct |
45 |
Correct |
517 ms |
68656 KB |
Output is correct |
46 |
Correct |
486 ms |
68340 KB |
Output is correct |
47 |
Correct |
307 ms |
55176 KB |
Output is correct |
48 |
Correct |
203 ms |
54112 KB |
Output is correct |
49 |
Correct |
265 ms |
54272 KB |
Output is correct |
50 |
Correct |
411 ms |
65148 KB |
Output is correct |
51 |
Correct |
391 ms |
68500 KB |
Output is correct |