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>
using namespace std;
typedef long long ll;
#define int long long
//#define endl '\n'
#define F first
#define S second
int const M = 1e6 + 10 , N = 1e3 + 10 , mod = 1e9 + 7;
ll T , n , m , k , cost , x , y , s , t , u , v , type , ans = 1e18 , dis[6][M] , cnt[M] , on[M] , U[M] , V[M];
int dx[] = {1 , -1 , 0 , 0} , dy[] = {0 , 0 , 1 , -1};
priority_queue<pair<ll , ll> , vector<pair<ll , ll>> , greater<pair<ll , ll>>>q;
vector<pair<ll , ll>>adj[M];
vector<ll>graph[M] , top;
bool vis[M];
inline void Dijkstra(int start) {
q.push({0 , start});
while(q.size()) {
int node = q.top().S;
int cost = q.top().F;
q.pop();
if(dis[type][node] || node == start && cost) continue;
dis[type][node] = cost;
for(auto next : adj[node]) q.push({cost + next.S , next.F});
}
}
inline void GetPath(int node) {
vis[node] = 1;
for(auto next : adj[node]) {
int kid = next.F;
if(dis[3][kid] + dis[4][kid] != dis[3][t] || vis[kid]) continue;
graph[node].push_back(kid);
graph[kid].push_back(node);
++cnt[node] , ++cnt[kid];
on[node] = 1; on[kid] = 1;
GetPath(kid);
}
}
inline void Bfs() {
queue<ll>Q;
Q.push(s);
while(Q.size()) {
int node = Q.front();
Q.pop();
top.push_back(node);
for(auto next : graph[node]) {
--cnt[next];
if(cnt[next] == 1) Q.push(next);
}
}
top.push_back(t);
}
main() {
ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
cin >> n >> m >> s >> t >> u >> v;
for(int i = 1 ; i <= m ; ++i) {
cin >> x >> y >> cost;
adj[x].push_back({y , cost});
adj[y].push_back({x , cost});
}
type = 1; Dijkstra(u);
type = 2; Dijkstra(v);
type = 3; Dijkstra(s);
type = 4; Dijkstra(t);
GetPath(s);
Bfs();
for(int i = 1 ; i <= n ; ++i) U[i] = V[i] = 1e18;
ans = dis[1][v];
for(auto node : top) {
ans = min(ans , dis[1][node] + V[node]);
ans = min(ans , dis[2][node] + U[node]);
U[node] = min(U[node] , dis[1][node]);
V[node] = min(V[node] , dis[2][node]);
for(auto next : graph[node]) U[next] = min(U[next] , U[node]) , V[next] = min(V[next] , V[node]);
}
cout << ans << endl;
return 0;
}
Compilation message (stderr)
commuter_pass.cpp: In function 'void Dijkstra(long long int)':
commuter_pass.cpp:22:41: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
22 | if(dis[type][node] || node == start && cost) continue;
| ~~~~~~~~~~~~~~^~~~~~~
commuter_pass.cpp: At global scope:
commuter_pass.cpp:57:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
57 | 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... |