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 plli pair<ll, int>
using namespace std;
const int N = 1e5 + 2;
int n, m, s, t, a, b;
vector<pair<int, ll>>adj[N];
vector<tuple<int, int, ll>>edge;
ll dist[N], distB[N];
void st1(){
for(int i = 1; i <= n; i++) dist[i] = distB[i] = 1e18;
priority_queue<plli, vector<plli>, greater<plli>>pq;
//shortest path from b to all
pq.emplace(0LL, b);
distB[b] = 0;
while(!pq.empty()){
auto [curW, u] = pq.top(); pq.pop();
for(auto &[v, w]: adj[u]){
if(distB[v] > curW + w){
distB[v] = curW + w;
pq.emplace(distB[v], v);
}
}
}
//shortest path from s to t????
pq.emplace(0LL, s);
dist[s] = 0;
vector<int>p[n + 1];
while(!pq.empty()){
auto [curW, u] = pq.top(); pq.pop();
for(auto &[v, w]: adj[u]){
if(dist[v] > curW + w){
p[v].clear();
p[v].push_back(u);
dist[v] = curW + w;
pq.emplace(dist[v], v);
} else if(dist[v] == curW + w){
p[v].push_back(u);
}
}
}
queue<int>q; q.push(t);
ll ans = 1e18;
while(!q.empty()){
int cur = q.front(); q.pop();
ans = min(ans, distB[cur]);
for(auto &nxt: p[cur]) q.push(nxt);
}
cout << ans << '\n';
}
void cape(){
vector<pair<int, ll>>adj1[N];
int p[N];
for(int i = 1; i <= n; i++){
dist[i] = 1e18;
p[i] = i;
}
priority_queue<plli, vector<plli>, greater<plli>>pq;
pq.emplace(0LL, s);
while(!pq.empty()){
auto [curW, u] = pq.top(); pq.pop();
for(auto &[v, w]: adj[u]){
if(dist[v] <= curW + w) continue;
dist[v] = curW + w;
p[v] = u;
pq.emplace(dist[v], v);
}
}
set<pair<int, int>>st;
int cur = t;
while(cur != s){
st.insert({cur, p[cur]});
st.insert({p[cur], cur});
cur = p[cur];
}
for(auto &[u, v, w]: edge){
if(st.count({u, v})) w = 0;
adj1[u].emplace_back(v, w);
adj1[v].emplace_back(u, w);
}
for(int i = 1; i <= n; i++) dist[i] = 1e18;
pq.emplace(0LL, a);
dist[a] = 0;
while(!pq.empty()){
auto [curW, u] = pq.top(); pq.pop();
for(auto &[v, w]: adj1[u]){
if(dist[v] <= curW + w) continue;
dist[v] = curW + w;
pq.emplace(dist[v], v);
}
}
cout << dist[b] << '\n';
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m >> s >> t >> a >> b;
while(m--){
int u, v, w; cin >> u >> v >> w;
edge.emplace_back(u, v, w);
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
if(s == a) st1();
else cape();
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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |