#include<bits/stdc++.h>
#define ll long long
#define f first
#define sc second
#define pb push_back
using namespace std;
ll a,b,c,d,i,e,f,g,n,m,k,l,ans,t,s,u,v1;
ll dist[5][100005],dist1[100005],fix[100005],dp[100005];
vector < pair < ll , ll > > v[200005];
priority_queue < pair <ll,ll> > pq;
void dijkstra(ll x,ll y) {
for(ll i=1;i<=n;i++) {
dist[y][i]=1e18;
}
dist[y][x]=0;
pq.push({0,x});
while(pq.size()) {
a=-pq.top().f;
b=pq.top().sc;
pq.pop();
for(ll i=0;i<v[b].size();i++) {
if(dist[y][v[b][i].f]>a+v[b][i].sc) {
dist[y][v[b][i].f]=a+v[b][i].sc;
pq.push({-dist[y][v[b][i].f],v[b][i].f});
}
}
}
}
void dijkstra1(ll x,ll y) {
for(ll i=1;i<=n;i++) {
dist1[i]=1e18;
fix[i]=0;
dp[i]=dist[3][i];
}
dist1[x]=0;
fix[x]=1;
pq.push({0,x});
while(pq.size()) {
a=-pq.top().f;
b=pq.top().sc;
pq.pop();
for(ll i=0;i<v[b].size();i++) {
if(dist1[b]+v[b][i].sc+dist[y][v[b][i].f]==dist[1][t]) {
fix[b]=1; fix[v[b][i].f]=1;
dp[v[b][i].f]=min(dp[v[b][i].f],dp[b]);
}
if(dist1[v[b][i].f]>a+v[b][i].sc) {
dist1[v[b][i].f]=a+v[b][i].sc;
pq.push({-dist1[v[b][i].f],v[b][i].f});
}
}
}
for(ll i=1;i<=n;i++) {
if(fix[i]==0) continue;
ans=min(ans,dp[i]+dist[4][i]);
}
}
int main() {
cin>>n>>m>>s>>t>>u>>v1;
for(ll i=1;i<=m;i++) {
cin>>a>>b>>c;
v[a].pb({b,c});
v[b].pb({a,c});
}
ans=1e18;
dijkstra(s,1); dijkstra(t,2); dijkstra(u,3); dijkstra(v1,4);
dijkstra1(s,2); dijkstra1(t,1);
cout<<min(ans,dist[3][v1]);
}
Compilation message
commuter_pass.cpp: In function 'void dijkstra(long long int, long long int)':
commuter_pass.cpp:21:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for(ll i=0;i<v[b].size();i++) {
| ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'void dijkstra1(long long int, long long int)':
commuter_pass.cpp:42:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(ll i=0;i<v[b].size();i++) {
| ~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
584 ms |
25984 KB |
Output is correct |
2 |
Correct |
626 ms |
25532 KB |
Output is correct |
3 |
Correct |
623 ms |
25708 KB |
Output is correct |
4 |
Correct |
542 ms |
25824 KB |
Output is correct |
5 |
Correct |
550 ms |
25128 KB |
Output is correct |
6 |
Correct |
694 ms |
25940 KB |
Output is correct |
7 |
Correct |
580 ms |
25328 KB |
Output is correct |
8 |
Correct |
599 ms |
25444 KB |
Output is correct |
9 |
Correct |
587 ms |
26064 KB |
Output is correct |
10 |
Correct |
478 ms |
26036 KB |
Output is correct |
11 |
Correct |
221 ms |
17696 KB |
Output is correct |
12 |
Correct |
615 ms |
25976 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
650 ms |
25648 KB |
Output is correct |
2 |
Correct |
638 ms |
25368 KB |
Output is correct |
3 |
Correct |
670 ms |
25308 KB |
Output is correct |
4 |
Correct |
622 ms |
25328 KB |
Output is correct |
5 |
Correct |
663 ms |
25344 KB |
Output is correct |
6 |
Correct |
642 ms |
25648 KB |
Output is correct |
7 |
Correct |
654 ms |
25312 KB |
Output is correct |
8 |
Correct |
655 ms |
25320 KB |
Output is correct |
9 |
Correct |
681 ms |
25336 KB |
Output is correct |
10 |
Correct |
667 ms |
25360 KB |
Output is correct |
11 |
Correct |
211 ms |
17760 KB |
Output is correct |
12 |
Correct |
602 ms |
25832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
6732 KB |
Output is correct |
2 |
Correct |
5 ms |
5068 KB |
Output is correct |
3 |
Correct |
4 ms |
5068 KB |
Output is correct |
4 |
Correct |
48 ms |
8512 KB |
Output is correct |
5 |
Correct |
25 ms |
6772 KB |
Output is correct |
6 |
Correct |
6 ms |
5144 KB |
Output is correct |
7 |
Correct |
7 ms |
5324 KB |
Output is correct |
8 |
Correct |
8 ms |
5324 KB |
Output is correct |
9 |
Correct |
5 ms |
5068 KB |
Output is correct |
10 |
Correct |
25 ms |
6720 KB |
Output is correct |
11 |
Correct |
4 ms |
5008 KB |
Output is correct |
12 |
Correct |
4 ms |
5068 KB |
Output is correct |
13 |
Correct |
4 ms |
5068 KB |
Output is correct |
14 |
Correct |
5 ms |
5068 KB |
Output is correct |
15 |
Correct |
5 ms |
5068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
584 ms |
25984 KB |
Output is correct |
2 |
Correct |
626 ms |
25532 KB |
Output is correct |
3 |
Correct |
623 ms |
25708 KB |
Output is correct |
4 |
Correct |
542 ms |
25824 KB |
Output is correct |
5 |
Correct |
550 ms |
25128 KB |
Output is correct |
6 |
Correct |
694 ms |
25940 KB |
Output is correct |
7 |
Correct |
580 ms |
25328 KB |
Output is correct |
8 |
Correct |
599 ms |
25444 KB |
Output is correct |
9 |
Correct |
587 ms |
26064 KB |
Output is correct |
10 |
Correct |
478 ms |
26036 KB |
Output is correct |
11 |
Correct |
221 ms |
17696 KB |
Output is correct |
12 |
Correct |
615 ms |
25976 KB |
Output is correct |
13 |
Correct |
650 ms |
25648 KB |
Output is correct |
14 |
Correct |
638 ms |
25368 KB |
Output is correct |
15 |
Correct |
670 ms |
25308 KB |
Output is correct |
16 |
Correct |
622 ms |
25328 KB |
Output is correct |
17 |
Correct |
663 ms |
25344 KB |
Output is correct |
18 |
Correct |
642 ms |
25648 KB |
Output is correct |
19 |
Correct |
654 ms |
25312 KB |
Output is correct |
20 |
Correct |
655 ms |
25320 KB |
Output is correct |
21 |
Correct |
681 ms |
25336 KB |
Output is correct |
22 |
Correct |
667 ms |
25360 KB |
Output is correct |
23 |
Correct |
211 ms |
17760 KB |
Output is correct |
24 |
Correct |
602 ms |
25832 KB |
Output is correct |
25 |
Correct |
26 ms |
6732 KB |
Output is correct |
26 |
Correct |
5 ms |
5068 KB |
Output is correct |
27 |
Correct |
4 ms |
5068 KB |
Output is correct |
28 |
Correct |
48 ms |
8512 KB |
Output is correct |
29 |
Correct |
25 ms |
6772 KB |
Output is correct |
30 |
Correct |
6 ms |
5144 KB |
Output is correct |
31 |
Correct |
7 ms |
5324 KB |
Output is correct |
32 |
Correct |
8 ms |
5324 KB |
Output is correct |
33 |
Correct |
5 ms |
5068 KB |
Output is correct |
34 |
Correct |
25 ms |
6720 KB |
Output is correct |
35 |
Correct |
4 ms |
5008 KB |
Output is correct |
36 |
Correct |
4 ms |
5068 KB |
Output is correct |
37 |
Correct |
4 ms |
5068 KB |
Output is correct |
38 |
Correct |
5 ms |
5068 KB |
Output is correct |
39 |
Correct |
5 ms |
5068 KB |
Output is correct |
40 |
Correct |
577 ms |
25988 KB |
Output is correct |
41 |
Correct |
648 ms |
25964 KB |
Output is correct |
42 |
Correct |
647 ms |
26100 KB |
Output is correct |
43 |
Correct |
250 ms |
17956 KB |
Output is correct |
44 |
Correct |
233 ms |
17744 KB |
Output is correct |
45 |
Correct |
506 ms |
24864 KB |
Output is correct |
46 |
Correct |
488 ms |
24652 KB |
Output is correct |
47 |
Correct |
565 ms |
25776 KB |
Output is correct |
48 |
Correct |
232 ms |
17220 KB |
Output is correct |
49 |
Correct |
494 ms |
25476 KB |
Output is correct |
50 |
Correct |
541 ms |
25100 KB |
Output is correct |
51 |
Correct |
499 ms |
24824 KB |
Output is correct |