#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repb(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define all(A) A.begin(),A.end()
#define allr(A) A.rbegin(),A.rend()
#define precise(i) fixed << setprecision(i)
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define err() cout<<"\n==================================\n";
#define errA(A) for(auto i:A) cout<<i<<" "; cout<<"\n";
#define err1(a) cout<<#a<<" "<<a<<"\n";
#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<"\n";
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<"\n";
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<"\n";
const int logN = 20;
const int M = 1000000007;
const int INF = 1e17;
#define PI 3.14159265;
const int N = 200005;
#define Pii pair<int,int>
#define Vi vector<int>
#define Vpii vector<Pii>
#define PQ priority_queue<int>
void setIO(string d_name = "") {
ios_base::sync_with_stdio(0); cin.tie(0);
if(sz(d_name)){
freopen((d_name+".in").c_str(), "r", stdin);
freopen((d_name+".out").c_str(), "w", stdout);
}
}
Vpii adj[100001];
void dijkstra1(int start, Vi& dist)
{
dist[start]= 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push(mp(0, start));
while(!pq.empty())
{
int d, x;
tie(d, x)= pq.top();
pq.pop();
if(dist[x] != d)
{
continue;
}
for(auto e: adj[x])
{
if(dist[e.fi] > dist[x] + e.se)
{
dist[e.fi]= dist[x]+e.se;
pq.push(mp(dist[e.fi], e.fi));
}
}
}
}
int dijkstra2(int start, int end, Vi& dist1, Vi& dist2)
{
Vi dist(100001);
Vi visited(100001);
Vi mi1(100001, INF);
Vi mi2(100001, INF);
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
pq.push(mp(0, mp(start, 0)));
while(!pq.empty())
{
int d, x, p;
pair<int, pair<int, int>> t= pq.top();
pq.pop();
d= t.fi;
x= t.se.fi;
p= t.se.se;
if(!visited[x])
{
visited[x]= 1;
dist[x]= d;
mi1[x]= min(dist1[x], mi1[p]);
mi2[x]= min(dist2[x], mi2[p]);
for(auto e: adj[x])
{
pq.push(mp(dist[x]+e.se, mp(e.fi, x)));
}
}
else if(dist[x] == d)
{
if((min(mi1[p], dist1[x]) + min(mi2[p], dist2[x])) < (mi1[x] + mi2[x]))
{
mi1[x]= min(mi1[p], dist1[x]);
mi2[x]= min(mi2[p], dist2[x]);
}
}
}
return (mi1[end] + mi2[end]);
}
int32_t main()
{
setIO();
int n, m;
cin>>n>>m;
int s, t;
cin>>s>>t;
int u, v;
cin>>u>>v;
rep(_,0,m)
{
int a, b, c;
cin>>a>>b>>c;
adj[a].pb(mp(b, c));
adj[b].pb(mp(a, c));
}
Vi dist1(n+1, INF);
Vi dist2(n+1, INF);
dijkstra1(u, dist1);
dijkstra1(v, dist2);
int ans= dist1[v];
ans= min(ans, dijkstra2(s, t, dist1, dist2));
ans= min(ans, dijkstra2(t, s, dist1, dist2));
cout<<ans;
return 0;
}
Compilation message
commuter_pass.cpp: In function 'void setIO(std::string)':
commuter_pass.cpp:40:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | freopen((d_name+".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:41:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | freopen((d_name+".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
497 ms |
29164 KB |
Output is correct |
2 |
Correct |
510 ms |
28732 KB |
Output is correct |
3 |
Correct |
490 ms |
28116 KB |
Output is correct |
4 |
Correct |
540 ms |
28304 KB |
Output is correct |
5 |
Correct |
466 ms |
25160 KB |
Output is correct |
6 |
Correct |
504 ms |
29044 KB |
Output is correct |
7 |
Correct |
481 ms |
28596 KB |
Output is correct |
8 |
Correct |
491 ms |
29064 KB |
Output is correct |
9 |
Correct |
514 ms |
29200 KB |
Output is correct |
10 |
Correct |
443 ms |
29076 KB |
Output is correct |
11 |
Correct |
148 ms |
14148 KB |
Output is correct |
12 |
Correct |
509 ms |
29404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
476 ms |
28928 KB |
Output is correct |
2 |
Correct |
462 ms |
25052 KB |
Output is correct |
3 |
Correct |
496 ms |
28332 KB |
Output is correct |
4 |
Correct |
458 ms |
25172 KB |
Output is correct |
5 |
Correct |
458 ms |
24968 KB |
Output is correct |
6 |
Correct |
474 ms |
28228 KB |
Output is correct |
7 |
Correct |
467 ms |
24912 KB |
Output is correct |
8 |
Correct |
476 ms |
25044 KB |
Output is correct |
9 |
Correct |
457 ms |
24908 KB |
Output is correct |
10 |
Correct |
470 ms |
28208 KB |
Output is correct |
11 |
Correct |
179 ms |
13892 KB |
Output is correct |
12 |
Correct |
486 ms |
28260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
8672 KB |
Output is correct |
2 |
Correct |
5 ms |
5836 KB |
Output is correct |
3 |
Correct |
6 ms |
5836 KB |
Output is correct |
4 |
Correct |
57 ms |
11552 KB |
Output is correct |
5 |
Correct |
31 ms |
9908 KB |
Output is correct |
6 |
Correct |
7 ms |
5964 KB |
Output is correct |
7 |
Correct |
7 ms |
6128 KB |
Output is correct |
8 |
Correct |
9 ms |
6240 KB |
Output is correct |
9 |
Correct |
6 ms |
5964 KB |
Output is correct |
10 |
Correct |
30 ms |
9784 KB |
Output is correct |
11 |
Correct |
5 ms |
5836 KB |
Output is correct |
12 |
Correct |
5 ms |
5812 KB |
Output is correct |
13 |
Correct |
6 ms |
5836 KB |
Output is correct |
14 |
Correct |
6 ms |
5900 KB |
Output is correct |
15 |
Correct |
6 ms |
5940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
497 ms |
29164 KB |
Output is correct |
2 |
Correct |
510 ms |
28732 KB |
Output is correct |
3 |
Correct |
490 ms |
28116 KB |
Output is correct |
4 |
Correct |
540 ms |
28304 KB |
Output is correct |
5 |
Correct |
466 ms |
25160 KB |
Output is correct |
6 |
Correct |
504 ms |
29044 KB |
Output is correct |
7 |
Correct |
481 ms |
28596 KB |
Output is correct |
8 |
Correct |
491 ms |
29064 KB |
Output is correct |
9 |
Correct |
514 ms |
29200 KB |
Output is correct |
10 |
Correct |
443 ms |
29076 KB |
Output is correct |
11 |
Correct |
148 ms |
14148 KB |
Output is correct |
12 |
Correct |
509 ms |
29404 KB |
Output is correct |
13 |
Correct |
476 ms |
28928 KB |
Output is correct |
14 |
Correct |
462 ms |
25052 KB |
Output is correct |
15 |
Correct |
496 ms |
28332 KB |
Output is correct |
16 |
Correct |
458 ms |
25172 KB |
Output is correct |
17 |
Correct |
458 ms |
24968 KB |
Output is correct |
18 |
Correct |
474 ms |
28228 KB |
Output is correct |
19 |
Correct |
467 ms |
24912 KB |
Output is correct |
20 |
Correct |
476 ms |
25044 KB |
Output is correct |
21 |
Correct |
457 ms |
24908 KB |
Output is correct |
22 |
Correct |
470 ms |
28208 KB |
Output is correct |
23 |
Correct |
179 ms |
13892 KB |
Output is correct |
24 |
Correct |
486 ms |
28260 KB |
Output is correct |
25 |
Correct |
31 ms |
8672 KB |
Output is correct |
26 |
Correct |
5 ms |
5836 KB |
Output is correct |
27 |
Correct |
6 ms |
5836 KB |
Output is correct |
28 |
Correct |
57 ms |
11552 KB |
Output is correct |
29 |
Correct |
31 ms |
9908 KB |
Output is correct |
30 |
Correct |
7 ms |
5964 KB |
Output is correct |
31 |
Correct |
7 ms |
6128 KB |
Output is correct |
32 |
Correct |
9 ms |
6240 KB |
Output is correct |
33 |
Correct |
6 ms |
5964 KB |
Output is correct |
34 |
Correct |
30 ms |
9784 KB |
Output is correct |
35 |
Correct |
5 ms |
5836 KB |
Output is correct |
36 |
Correct |
5 ms |
5812 KB |
Output is correct |
37 |
Correct |
6 ms |
5836 KB |
Output is correct |
38 |
Correct |
6 ms |
5900 KB |
Output is correct |
39 |
Correct |
6 ms |
5940 KB |
Output is correct |
40 |
Correct |
475 ms |
28820 KB |
Output is correct |
41 |
Correct |
490 ms |
29392 KB |
Output is correct |
42 |
Correct |
519 ms |
29248 KB |
Output is correct |
43 |
Correct |
161 ms |
14252 KB |
Output is correct |
44 |
Correct |
148 ms |
14128 KB |
Output is correct |
45 |
Correct |
465 ms |
23836 KB |
Output is correct |
46 |
Correct |
448 ms |
23888 KB |
Output is correct |
47 |
Correct |
502 ms |
25108 KB |
Output is correct |
48 |
Correct |
163 ms |
14236 KB |
Output is correct |
49 |
Correct |
485 ms |
27812 KB |
Output is correct |
50 |
Correct |
436 ms |
23928 KB |
Output is correct |
51 |
Correct |
421 ms |
24052 KB |
Output is correct |