#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll dis[5][100005];
bool vis[100005];
vector<pair<ll, ll>>adj[100005];
vector<ll>adj2[100005];
class cmp{
public:
bool operator()(pair<ll, ll>p1, pair<ll, ll>p2){
return p1.second>p2.second;
}
};
void dijkstra(int src, int idx){
for(int i=0;i<100005;i++) dis[idx][i]=1e16;
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, cmp>pq;
dis[idx][src]=0;
pq.push({src, 0});
memset(vis, 0, sizeof vis);
while(!pq.empty()){
ll x=pq.top().first, w=pq.top().second;
pq.pop();
if(vis[x]) continue;
vis[x]=true;
for(auto u:adj[x]){
ll y=u.first, cw=u.second;
if(dis[idx][y]>cw+w){
dis[idx][y]=cw+w;
pq.push({y, dis[idx][y]});
}
}
}
}
vector<int>tour;
void dfs(int x){
vis[x]=true;
for(int y:adj2[x]){
if(vis[y]) continue;
dfs(y);
}
tour.push_back(x);
}
ll mini[100005];
ll solve(int a, int b){
ll ans=LONG_LONG_MAX;
for(int i:tour){
mini[i]=dis[b][i];
for(int j:adj2[i]){
mini[i]=min(mini[i], mini[j]);
}
ans=min(ans, dis[a][i]+mini[i]);
}
return ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m, s, t, u, v;
cin>>n>>m>>s>>t>>u>>v;
vector<pair<pair<ll, ll>, ll>>edges;
for(int i=1;i<=m;i++){
ll x, y, w;
cin>>x>>y>>w;
edges.push_back({{x, y}, w});
adj[x].push_back({y, w});
adj[y].push_back({x, w});
}
dijkstra(s, 1);
dijkstra(t, 2);
dijkstra(u, 3);
dijkstra(v, 4);
/*for(int i=1;i<=4;i++){
for(int j=1;j<=n;j++){
cout<<dis[i][j]<<" ";
}
cout<<endl;
}*/
for(auto i:edges){
ll x=i.first.first, y=i.first.second, w=i.second;
if(dis[1][x]+dis[2][y]+w==dis[1][t]) adj2[x].push_back(y);
else if(dis[1][y]+dis[2][x]+w==dis[1][t]) adj2[y].push_back(x);
}
memset(vis, false, sizeof vis);
for(int i=1;i<=n;i++){
if(!vis[i]) dfs(i);
}
ll ans=dis[3][v];
ans=min(ans, solve(3, 4));
ans=min(ans, solve(4, 3));
cout<<ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
354 ms |
31128 KB |
Output is correct |
2 |
Correct |
352 ms |
29720 KB |
Output is correct |
3 |
Correct |
369 ms |
32280 KB |
Output is correct |
4 |
Correct |
396 ms |
31256 KB |
Output is correct |
5 |
Correct |
352 ms |
29592 KB |
Output is correct |
6 |
Correct |
386 ms |
31196 KB |
Output is correct |
7 |
Correct |
448 ms |
29792 KB |
Output is correct |
8 |
Correct |
464 ms |
29720 KB |
Output is correct |
9 |
Correct |
358 ms |
30388 KB |
Output is correct |
10 |
Correct |
304 ms |
30224 KB |
Output is correct |
11 |
Correct |
256 ms |
22308 KB |
Output is correct |
12 |
Correct |
402 ms |
30360 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
424 ms |
30656 KB |
Output is correct |
2 |
Correct |
463 ms |
30616 KB |
Output is correct |
3 |
Correct |
376 ms |
30720 KB |
Output is correct |
4 |
Correct |
397 ms |
30028 KB |
Output is correct |
5 |
Correct |
409 ms |
30248 KB |
Output is correct |
6 |
Correct |
431 ms |
31648 KB |
Output is correct |
7 |
Correct |
408 ms |
32360 KB |
Output is correct |
8 |
Correct |
365 ms |
30236 KB |
Output is correct |
9 |
Correct |
375 ms |
30548 KB |
Output is correct |
10 |
Correct |
359 ms |
30744 KB |
Output is correct |
11 |
Correct |
193 ms |
23464 KB |
Output is correct |
12 |
Correct |
375 ms |
32152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
10552 KB |
Output is correct |
2 |
Correct |
9 ms |
8320 KB |
Output is correct |
3 |
Correct |
10 ms |
8352 KB |
Output is correct |
4 |
Correct |
28 ms |
12588 KB |
Output is correct |
5 |
Correct |
18 ms |
10424 KB |
Output is correct |
6 |
Correct |
10 ms |
8448 KB |
Output is correct |
7 |
Correct |
10 ms |
8576 KB |
Output is correct |
8 |
Correct |
11 ms |
8576 KB |
Output is correct |
9 |
Correct |
10 ms |
8448 KB |
Output is correct |
10 |
Correct |
17 ms |
10424 KB |
Output is correct |
11 |
Correct |
10 ms |
8320 KB |
Output is correct |
12 |
Correct |
9 ms |
8320 KB |
Output is correct |
13 |
Correct |
10 ms |
8320 KB |
Output is correct |
14 |
Correct |
10 ms |
8320 KB |
Output is correct |
15 |
Correct |
10 ms |
8320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
354 ms |
31128 KB |
Output is correct |
2 |
Correct |
352 ms |
29720 KB |
Output is correct |
3 |
Correct |
369 ms |
32280 KB |
Output is correct |
4 |
Correct |
396 ms |
31256 KB |
Output is correct |
5 |
Correct |
352 ms |
29592 KB |
Output is correct |
6 |
Correct |
386 ms |
31196 KB |
Output is correct |
7 |
Correct |
448 ms |
29792 KB |
Output is correct |
8 |
Correct |
464 ms |
29720 KB |
Output is correct |
9 |
Correct |
358 ms |
30388 KB |
Output is correct |
10 |
Correct |
304 ms |
30224 KB |
Output is correct |
11 |
Correct |
256 ms |
22308 KB |
Output is correct |
12 |
Correct |
402 ms |
30360 KB |
Output is correct |
13 |
Correct |
424 ms |
30656 KB |
Output is correct |
14 |
Correct |
463 ms |
30616 KB |
Output is correct |
15 |
Correct |
376 ms |
30720 KB |
Output is correct |
16 |
Correct |
397 ms |
30028 KB |
Output is correct |
17 |
Correct |
409 ms |
30248 KB |
Output is correct |
18 |
Correct |
431 ms |
31648 KB |
Output is correct |
19 |
Correct |
408 ms |
32360 KB |
Output is correct |
20 |
Correct |
365 ms |
30236 KB |
Output is correct |
21 |
Correct |
375 ms |
30548 KB |
Output is correct |
22 |
Correct |
359 ms |
30744 KB |
Output is correct |
23 |
Correct |
193 ms |
23464 KB |
Output is correct |
24 |
Correct |
375 ms |
32152 KB |
Output is correct |
25 |
Correct |
22 ms |
10552 KB |
Output is correct |
26 |
Correct |
9 ms |
8320 KB |
Output is correct |
27 |
Correct |
10 ms |
8352 KB |
Output is correct |
28 |
Correct |
28 ms |
12588 KB |
Output is correct |
29 |
Correct |
18 ms |
10424 KB |
Output is correct |
30 |
Correct |
10 ms |
8448 KB |
Output is correct |
31 |
Correct |
10 ms |
8576 KB |
Output is correct |
32 |
Correct |
11 ms |
8576 KB |
Output is correct |
33 |
Correct |
10 ms |
8448 KB |
Output is correct |
34 |
Correct |
17 ms |
10424 KB |
Output is correct |
35 |
Correct |
10 ms |
8320 KB |
Output is correct |
36 |
Correct |
9 ms |
8320 KB |
Output is correct |
37 |
Correct |
10 ms |
8320 KB |
Output is correct |
38 |
Correct |
10 ms |
8320 KB |
Output is correct |
39 |
Correct |
10 ms |
8320 KB |
Output is correct |
40 |
Correct |
358 ms |
31200 KB |
Output is correct |
41 |
Correct |
341 ms |
30232 KB |
Output is correct |
42 |
Correct |
348 ms |
30360 KB |
Output is correct |
43 |
Correct |
157 ms |
24612 KB |
Output is correct |
44 |
Correct |
160 ms |
24740 KB |
Output is correct |
45 |
Correct |
369 ms |
31384 KB |
Output is correct |
46 |
Correct |
354 ms |
31212 KB |
Output is correct |
47 |
Correct |
357 ms |
31012 KB |
Output is correct |
48 |
Correct |
151 ms |
22692 KB |
Output is correct |
49 |
Correct |
268 ms |
30632 KB |
Output is correct |
50 |
Correct |
367 ms |
30744 KB |
Output is correct |
51 |
Correct |
337 ms |
31384 KB |
Output is correct |