#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mx=1e5+9;
const ll inf=1e18;
ll dist[4][mx+9];
vector<pair<int,ll>>adj[mx];
int n,m,s,t,u,v;
ll dp[2][mx];ll l;
void dikjstra(int node,int cnt)
{
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater < pair<ll,int> >>q;
for(int i=0; i<=n; i++)
{
dist[cnt][i]=inf;
}
q.push({0,node});
dist[cnt][node]=0;
while(!q.empty())
{
pair<ll,int>me=q.top();
q.pop();
int x=me.second;
ll cost=me.first;
for(auto it:adj[x])
{
int node2=it.first;
if(cost+it.second<dist[cnt][it.first])
{ ll cost2=cost+it.second;
dist[cnt][it.first]=cost2;
q.push({(cost2),node2});
}
}
}
}
void dikjstra2(int node,int cnt)
{
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater < pair<ll,int> >>q;
bool vis[n+9];
for(int i=0; i<=n; i++)
{
// dist[cnt][i]=inf;
vis[i]=0;
}
q.push({0,node});
while(!q.empty())
{
pair<ll,int>me=q.top();
q.pop();
int x=me.second;
if(vis[x]){
continue;
}
vis[x]=1;
ll cost=me.first;
dp[cnt][x]=min(dist[3][x],dp[cnt][x]);
for(auto it:adj[x])
{
int node2=it.first;
if(cost+it.second<=dist[cnt][it.first])
{
dp[cnt][node2]=min( dp[cnt][node2],dp[cnt][x]);
ll cost2=cost+it.second;
q.push({(cost2),node2});
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin>>n>>m>>s>>t>>u>>v;
for(int i=0; i<m; i++)
{
ll x,y,c;
cin>>x>>y>>c;
adj[x].push_back({y,c});
adj[y].push_back({x,c});
}
dikjstra(v,3);
dikjstra(u,2);
dikjstra(s,0);
dikjstra(t,1);
l=dist[0][t];
for(int i=1; i<=n; i++)
{
dp[0][i]=dp[1][i]=inf;
}
dikjstra2(t,1);
dikjstra2(s,0);
ll ans=inf;
for(int i=1; i<=n; i++)
{
if(dist[0][i]+dist[1][i]==l)
{
ans=min(dist[2][i]+dp[0][i],ans);
ans=min(dist[2][i]+dp[1][i],ans);
}
}
ans=min(ans,dist[2][v]);
cout<<ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
337 ms |
19516 KB |
Output is correct |
2 |
Correct |
330 ms |
18208 KB |
Output is correct |
3 |
Correct |
319 ms |
19252 KB |
Output is correct |
4 |
Correct |
326 ms |
20872 KB |
Output is correct |
5 |
Correct |
333 ms |
18748 KB |
Output is correct |
6 |
Correct |
348 ms |
19516 KB |
Output is correct |
7 |
Correct |
337 ms |
18100 KB |
Output is correct |
8 |
Correct |
344 ms |
18260 KB |
Output is correct |
9 |
Correct |
329 ms |
18772 KB |
Output is correct |
10 |
Correct |
284 ms |
19880 KB |
Output is correct |
11 |
Correct |
141 ms |
12692 KB |
Output is correct |
12 |
Correct |
347 ms |
18184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
399 ms |
18680 KB |
Output is correct |
2 |
Correct |
353 ms |
18020 KB |
Output is correct |
3 |
Correct |
342 ms |
18096 KB |
Output is correct |
4 |
Correct |
345 ms |
18044 KB |
Output is correct |
5 |
Correct |
345 ms |
18164 KB |
Output is correct |
6 |
Correct |
329 ms |
19828 KB |
Output is correct |
7 |
Correct |
350 ms |
19424 KB |
Output is correct |
8 |
Correct |
348 ms |
19240 KB |
Output is correct |
9 |
Correct |
341 ms |
19264 KB |
Output is correct |
10 |
Correct |
345 ms |
19268 KB |
Output is correct |
11 |
Correct |
132 ms |
13836 KB |
Output is correct |
12 |
Correct |
337 ms |
20064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
4308 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
21 ms |
5860 KB |
Output is correct |
5 |
Correct |
9 ms |
4052 KB |
Output is correct |
6 |
Correct |
2 ms |
2772 KB |
Output is correct |
7 |
Correct |
2 ms |
2772 KB |
Output is correct |
8 |
Correct |
3 ms |
2900 KB |
Output is correct |
9 |
Correct |
2 ms |
2772 KB |
Output is correct |
10 |
Correct |
10 ms |
4280 KB |
Output is correct |
11 |
Correct |
2 ms |
2644 KB |
Output is correct |
12 |
Correct |
1 ms |
2644 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
2 ms |
2772 KB |
Output is correct |
15 |
Correct |
2 ms |
2772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
337 ms |
19516 KB |
Output is correct |
2 |
Correct |
330 ms |
18208 KB |
Output is correct |
3 |
Correct |
319 ms |
19252 KB |
Output is correct |
4 |
Correct |
326 ms |
20872 KB |
Output is correct |
5 |
Correct |
333 ms |
18748 KB |
Output is correct |
6 |
Correct |
348 ms |
19516 KB |
Output is correct |
7 |
Correct |
337 ms |
18100 KB |
Output is correct |
8 |
Correct |
344 ms |
18260 KB |
Output is correct |
9 |
Correct |
329 ms |
18772 KB |
Output is correct |
10 |
Correct |
284 ms |
19880 KB |
Output is correct |
11 |
Correct |
141 ms |
12692 KB |
Output is correct |
12 |
Correct |
347 ms |
18184 KB |
Output is correct |
13 |
Correct |
399 ms |
18680 KB |
Output is correct |
14 |
Correct |
353 ms |
18020 KB |
Output is correct |
15 |
Correct |
342 ms |
18096 KB |
Output is correct |
16 |
Correct |
345 ms |
18044 KB |
Output is correct |
17 |
Correct |
345 ms |
18164 KB |
Output is correct |
18 |
Correct |
329 ms |
19828 KB |
Output is correct |
19 |
Correct |
350 ms |
19424 KB |
Output is correct |
20 |
Correct |
348 ms |
19240 KB |
Output is correct |
21 |
Correct |
341 ms |
19264 KB |
Output is correct |
22 |
Correct |
345 ms |
19268 KB |
Output is correct |
23 |
Correct |
132 ms |
13836 KB |
Output is correct |
24 |
Correct |
337 ms |
20064 KB |
Output is correct |
25 |
Correct |
11 ms |
4308 KB |
Output is correct |
26 |
Correct |
2 ms |
2644 KB |
Output is correct |
27 |
Correct |
2 ms |
2644 KB |
Output is correct |
28 |
Correct |
21 ms |
5860 KB |
Output is correct |
29 |
Correct |
9 ms |
4052 KB |
Output is correct |
30 |
Correct |
2 ms |
2772 KB |
Output is correct |
31 |
Correct |
2 ms |
2772 KB |
Output is correct |
32 |
Correct |
3 ms |
2900 KB |
Output is correct |
33 |
Correct |
2 ms |
2772 KB |
Output is correct |
34 |
Correct |
10 ms |
4280 KB |
Output is correct |
35 |
Correct |
2 ms |
2644 KB |
Output is correct |
36 |
Correct |
1 ms |
2644 KB |
Output is correct |
37 |
Correct |
2 ms |
2644 KB |
Output is correct |
38 |
Correct |
2 ms |
2772 KB |
Output is correct |
39 |
Correct |
2 ms |
2772 KB |
Output is correct |
40 |
Correct |
346 ms |
24240 KB |
Output is correct |
41 |
Correct |
337 ms |
23024 KB |
Output is correct |
42 |
Correct |
324 ms |
23112 KB |
Output is correct |
43 |
Correct |
124 ms |
14816 KB |
Output is correct |
44 |
Correct |
120 ms |
14788 KB |
Output is correct |
45 |
Correct |
329 ms |
23152 KB |
Output is correct |
46 |
Correct |
340 ms |
22792 KB |
Output is correct |
47 |
Correct |
346 ms |
25020 KB |
Output is correct |
48 |
Correct |
132 ms |
14340 KB |
Output is correct |
49 |
Correct |
316 ms |
24572 KB |
Output is correct |
50 |
Correct |
332 ms |
23052 KB |
Output is correct |
51 |
Correct |
320 ms |
22972 KB |
Output is correct |