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 ull unsigned long long
#define i128 __int128
#define F first
#define S second
#define pb push_back
#define pi pair<int,int>
#define pl pair<ll,ll>
using namespace std;
constexpr int debug = 0;
constexpr int N = 1e5+7;
vector<pl> adj[2*N];
ll dist[N][4]; //dist from s, t, u, v
ll best[N][2];
bool visited[N][2];
int n, m, s, t, u, v;
ll target;
void addEdge(ll a, ll b, ll val){
adj[a].pb({b, val});
adj[b].pb({a, val});
}
void dijkstra(int start, int num){
priority_queue<pl> Q;
dist[start][num] = 0;
Q.push({0, start});
while(!Q.empty()){
pl cur = Q.top();
Q.pop();
if(dist[cur.S][num] == -1) continue;
for(auto k: adj[cur.S]){
if(dist[k.F][num] == -1 || dist[k.F][num] > dist[cur.S][num]+k.S){
dist[k.F][num] = dist[cur.S][num]+k.S;
Q.push({-dist[k.F][num], k.F});
}
}
}
}
void dfs(int cur, bool mode){ //cur is the current vertex, mode determines whether dist from s or t should increase
visited[cur][mode] = 1;
if(best[cur][mode] == 0) best[cur][mode] = cur;
for(auto k: adj[cur]){
if(dist[k.F][0]+dist[k.F][1] == target){
if(dist[k.F][mode] > dist[cur][mode]){
if(!visited[k.F][mode]) dfs(k.F, mode);
if(dist[best[cur][mode]][3] > dist[best[k.F][mode]][3]) best[cur][mode] = best[k.F][mode];
}
}
}
if(mode){
(dist[best[cur][0]][3] < dist[best[cur][1]][3]) ? adj[cur].pb({best[cur][0]+n, 0}) : adj[cur].pb({best[cur][1]+n, 0});
}
if(debug) cout << "EXIT " << cur << ' ' << mode << ' ' << best[cur][mode] << endl;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m >> s >> t >> u >> v;
for(int i = 0; i < m; i++){
ll a1, a2, a3; cin >> a1 >> a2 >> a3;
addEdge(a1, a2, a3);
addEdge(a1+n, a2+n, a3);
}
for(int i = 0; i <= 2*n+1; i++){
for(int j = 0; j < 4; j++) dist[i][j] = -1;
if(i > 0) adj[i].pb({i+n, 0});
}
dijkstra(v, 3);
dijkstra(t, 1);
dijkstra(s, 0);
target = dist[t][0]; //distance from s to t
/*
for(int j = 0; j < 4; j++){
for(int i = 1; i <= n; i++){
if(debug) cout << "DISTANCE " << i << ' ' << dist[i][j] << endl;
}
}
*/
dfs(s, 0);
dfs(t, 1);
dijkstra(u,2);
cout << dist[v+n][2];
return 0;
}
# | 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... |