이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define newl '\n'
const int mod = 1e9+7;
const ll MAX = 0x3f3f3f3f3f3f3f3f;
vector<vector<pair<ll,ll>>> neighbors(1e5);
vector<ll> du(1e5+1, MAX/2);
vector<ll> dv(1e5+1, MAX/2);
vector<ll> dp(1e5+1, MAX/2);
vector<ll> dpu(1e5+1, MAX/2);
vector<ll> dpv(1e5+1, MAX/2);
const int mn = 1e5+1;
bool vis[mn];
ll ans;
void dijkstra(int s, vector<ll> &d) { // Source and destination
fill(vis, vis + mn, false);
using T = pair<ll,ll>; priority_queue<T,vector<T>,greater<T>> pq;
d[s] = 0; // The shortest path from a node to itself is 0
pq.push({0, s});
while (!pq.empty()) {
int pos = pq.top().second;
pq.pop();
if(vis[pos]==true){
continue;
}
vis[pos] = true;
for (auto x: neighbors[pos]) {
// If we can reach a neighbouring node faster,
// we update its minimum distance
int place; ll value;
tie(place, value) = x;
if (d[pos]+value < d[place]) {
d[place] = d[pos]+value;
pq.push({d[place], place});
}
}
}
}
void dijkstra2(int start, int end) { // Source and destination
fill(vis,vis+mn , false);
fill(dpu.begin(),dpu.end(),MAX/2);
fill(dpv.begin(), dpv.end(), MAX/2);
priority_queue<pair<ll,pair<int, int>>> pq;
pq.push({0, {start,0}});
dp[start] = 0;
while (pq.size()) {
ll cost, curr, last;
cost = pq.top().first;
curr = pq.top().second.first;
last = pq.top().second.second;
pq.pop();
if(vis[curr]!=true){
vis[curr] = true;
dp[curr] = -cost;
dpu[curr] = min(dpu[last], du[curr]);
dpv[curr] = min(dpv[last], dv[curr]);
for (auto x : neighbors[curr]) {
// If we can reach a neighbouring node faster,
// we update its minimum distance
int place; ll value;
tie(place,value) = x;
if(dp[place]> dp[curr]+value){
pq.push({cost-value,{place, curr}});
}
}
}else if(-cost == dp[curr]){
if(min(dpu[last], du[curr]) + min(dpv[last], dv[curr]) < dpu[curr]+dpv[curr]){
dpu[curr] = min(dpu[last], du[curr]);
dpv[curr] = min(dpv[last], dv[curr]);
}
}
}
ans = min(ans, dpu[end]+dpv[end]);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
//freopen("commuterpass.in", "r", stdin);
//freopen("nocross.out", "w", stdout);
int N,M,S,T,U,V,a,b,c;
cin >> N >> M;
cin >> S >> T >> U >> V;//s,t is free, U,V needs minimizing
S--;
T--;
U--;
V--;
for(int i=0; i<M; i++){
cin >> a >> b >> c;
a--;
b--;
neighbors[a].push_back(make_pair(b,c));
neighbors[b].push_back(make_pair(a,c));
}
dijkstra(U,du);
dijkstra(V, dv);
ans = du[V];
dijkstra2(S,T);
dijkstra2(T,S);
cout << ans << endl;
}
# | 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... |