이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
using namespace std;
const ll INF = 10000000000000000;
vector<vector<ll>> edges[100005];
ll dp1[2][100005];
ll dp2[2][100005];
ll distss[100005];
ll distst[100005];
ll distsu[100005];
ll distsv[100005];
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
FOR(i,0,2) FOR(j,0,100005) dp1[i][j] = INF, dp2[i][j] = INF;
FOR(i,0,100005) distss[i]=INF,distst[i]=INF,distsu[i]=INF,distsv[i]=INF;
ll n,m,s,t,u,v;
cin >> n >> m;
cin >> s >> t;
cin >> u >> v;
FOR(i,0,m){
ll a,b,c;
cin >> a >> b>> c;
edges[a].push_back({b,c});
edges[b].push_back({a,c});
}
priority_queue<vector<ll>> sus;
sus.push({0, u});
distsu[u] = 0;
while (sus.size()){
vector<ll> node = sus.top();
sus.pop();
node[0] = -node[0];
if (distsu[node[1]] != node[0]) continue;
for (auto&i : edges[node[1]]){
if (distsu[i[0]] > i[1] + distsu[node[1]]){
distsu[i[0]] = i[1] + distsu[node[1]];
sus.push({-distsu[i[0]], i[0]});
}
}
}
sus.push({0, v});
distsv[v] = 0;
while (sus.size()){
vector<ll> node = sus.top();
sus.pop();
node[0] = -node[0];
if (distsv[node[1]] != node[0]) continue;
for (auto&i : edges[node[1]]){
if (distsv[i[0]] > i[1] + distsv[node[1]]){
distsv[i[0]] = i[1] + distsv[node[1]];
sus.push({-distsv[i[0]], i[0]});
}
}
}
FOR(i,1,n+1){
dp1[0][i] = distsu[i];
dp1[1][i] = distsv[i];
dp2[0][i] = distsu[i];
dp2[1][i] = distsv[i];
}
sus.push({0, s});
distss[s] = 0;
while (sus.size()){
vector<ll> node = sus.top();
sus.pop();
node[0] = -node[0];
if (distss[node[1]] != node[0]) continue;
for (auto&i : edges[node[1]]){
if (distss[i[0]] > i[1] + distss[node[1]]){
distss[i[0]] = i[1] + distss[node[1]];
sus.push({-distss[i[0]], i[0]});
}
}
}
sus.push({0, t});
distst[t] = 0;
while (sus.size()){
vector<ll> node = sus.top();
sus.pop();
node[0] = -node[0];
if (distst[node[1]] != node[0]) continue;
for (auto&i : edges[node[1]]){
if (distst[i[0]] > i[1] + distst[node[1]]){
distst[i[0]] = i[1] + distst[node[1]];
sus.push({-distst[i[0]], i[0]});
}
}
}
set<ll> visited;
sus.push({0, s, distsu[s], distsv[s]});
distss[s] = 0;
dp1[0][s] = distsu[s];
dp1[1][s] = distsv[s];
visited.insert(s);
while (sus.size()){
vector<ll> node = sus.top();
sus.pop();
node[0] = -node[0];
if (distss[node[1]] != node[0]) continue;
for (auto&i : edges[node[1]]){
if (distss[i[0]] == i[1] + distss[node[1]] && visited.count(i[0])==0){
visited.insert(i[0]);
distss[i[0]] = i[1] + distss[node[1]];
sus.push({-distss[i[0]], i[0]});
dp1[0][i[0]] = min(dp1[0][i[0]], dp1[0][node[1]]);
dp1[1][i[0]] = min(dp1[1][i[0]], dp1[1][node[1]]);
} else if (distss[i[0]] == i[1] + distss[node[1]]){
dp1[0][i[0]] = min(dp1[0][i[0]], dp1[0][node[1]]);
dp1[1][i[0]] = min(dp1[1][i[0]], dp1[1][node[1]]);
}
}
}
visited.clear();
sus.push({0, t});
distst[t] = 0;
dp2[0][t] = distsu[t];
dp2[1][t] = distsv[t];
visited.insert(t);
while (sus.size()){
vector<ll> node = sus.top();
sus.pop();
node[0] = -node[0];
if (distst[node[1]] != node[0]){
continue;
}
for (auto&i : edges[node[1]]){
if (distst[i[0]] == i[1] + distst[node[1]] && visited.count(i[0])==0){
visited.insert(i[0]);
distst[i[0]] = i[1] + distst[node[1]];
sus.push({-distst[i[0]], i[0]});
dp2[0][i[0]] = min(dp2[0][i[0]], dp2[0][node[1]]);
dp2[1][i[0]] = min(dp2[1][i[0]], dp2[1][node[1]]);
} else if (distst[i[0]] == i[1] + distst[node[1]]){
dp2[0][i[0]] = min(dp2[0][i[0]], dp2[0][node[1]]);
dp2[1][i[0]] = min(dp2[1][i[0]], dp2[1][node[1]]);
}
}
}
ll opt = distss[t];
ll ans = INF;
FOR(i,1,n+1){
if (distss[i] + distst[i] != opt) continue;
ans = min(ans, dp1[0][i] + dp2[1][i]);
ans = min(ans, dp1[1][i] + dp2[0][i]);
}
cout << min(ans, distsu[v]) << 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... |