This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
const int N = 1e6+50, mod = 1e9+7, K = 31;
int n,m;
int S,T,U,V;
int x,y,w;
vector<pair<int,int>>gr[N];
ll D[5][N];
int A[5],ind[5];
ll dp[N];
inline void dijkstra(int x){
priority_queue<pair<ll,int>>q;
vector<int>fix(n+5,0);
int a = ind[x];
for(int i = 1; i <= n; i++){
D[a][i] = 1e18;
}
D[a][x] = 0;
q.push({0,x});
while(q.size()){
auto p = q.top();
q.pop();
int x = p.ss;
ll dist = -p.ff;
if(fix[x]) continue;
fix[x] = 1;
//cout << x << " " ;
for(auto pp : gr[x]){
int to = pp.ff;
ll w = pp.ss;
ll new_dist = dist + w;
if(D[a][to] > new_dist){
D[a][to] = new_dist;
q.push({-new_dist,to});
}
}
}
/*cout << a << endl;
for(int i = 1; i <= n; i++){
cout << D[a][i] << ' ';
}
cout << endl;*/
}
ll dist_st;
inline bool on_pass(int x){
return dist_st == (D[ind[S]][x] + D[ind[T]][x]);
}
inline void bfs(int x){
vector<pair<ll,int>>v;
for(int i = 1; i <= n; i++){
if(on_pass(i)){
v.pb({D[ind[x]][i],i});
}
}
sort(v.begin(),v.end());
for(int i = 0; i < v.size(); i++){
int x = v[i].ss;
//cout << x << endl;
dp[x] = min(dp[x],D[ind[U]][x]);
for(auto pp : gr[x]){
int to = pp.ff;
dp[x] = min(dp[x],dp[to]);
}
}
}
inline void test_case(){
cin >> n >> m;
for(int i = 1; i <= 4; i++){
cin >> A[i];
ind[A[i]] = i;
}
S = A[1]; T = A[2]; U = A[3]; V = A[4];
for(int i = 1; i <= m; i++){
cin >> x >> y >> w;
gr[x].pb({y,w});
gr[y].pb({x,w});
}
for(int i = 1; i <= 4; i++) dijkstra(A[i]);
dist_st = D[ind[S]][T];
//cout << dist_st << endl;
for(int i = 1; i <= n; i++) dp[i] = 1e18;
bfs(S);
bfs(T);
ll answer = D[ind[U]][V];
for(int i = 1; i <= n; i++){
answer = min(answer, dp[i] + D[ind[V]][i]);
}
cout << answer << endl;
}
main(){
ios::sync_with_stdio(0);
int T = 1;
//cin >> T;
for(int i = 1; i <= T; i++){
test_case();
}
}
Compilation message (stderr)
commuter_pass.cpp: In function 'void bfs(int)':
commuter_pass.cpp:76:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int>, std::allocator<std::pair<long long int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(int i = 0; i < v.size(); i++){
| ~~^~~~~~~~~~
commuter_pass.cpp: At global scope:
commuter_pass.cpp:118:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
118 | main(){
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |