이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 4e5 + 5;
int n, m;
int S, T, U, V;
vector<pair<int, int>> g[maxn];
ll dist[2][maxn];
bool vis[maxn];
void dij(int s, ll f[]){
priority_queue<pair<ll, int>, vector<pair<ll,int>>, greater<pair<ll,int>>> q;
for(int i = 1; i <= 4 * n; i ++) f[i] = 1e18;
q.push({0, s}); f[s] = 0;
while(q.size()){
auto [du, u] = q.top();
q.pop();
if(du != f[u]) continue;
for(auto [v, w] : g[u]){
if(f[v] > du + w){
f[v] = du + w;
q.push({f[v], v});
}
}
}
}
int main(){
cin >> n >> m >> S >> T >> U >> V;
for(int i = 1; i <= m; i ++){
int u, v, w; cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
g[u + 3 * n].push_back({3 * n + v, w});
g[v + 3 * n].push_back({3 * n + u, w});
}
dij(S, dist[0]);
dij(T, dist[1]);
queue <int> q;
q.push(S);
for(int i = 1; i <= n; i ++){
g[i].push_back({n + i, 0});
g[n + i].push_back({3 * n + i, 0});
g[2 * n + i].push_back({3 * n + i, 0});
g[i].push_back({2 * n + i, 0});
}
while(q.size()){
int u = q.front(); q.pop();
if(vis[u]) continue;
vis[u] = 1;
for(auto [v, w] : g[u]){
if(v > n) continue;
if(vis[v]) continue;
if(dist[0][u] + dist[1][v] + w == dist[1][S] || dist[1][u] + dist[0][v] + w == dist[1][S]){
g[n + u].push_back({n + v, 0});
q.push(v);
}
}
}
q.push(T);
for(int i = 0; i <= n; i ++) vis[i] = 0;
while(q.size()){
int u = q.front(); q.pop();
if(vis[u]) continue;
vis[u] = 1;
for(auto [v, w] : g[u]){
if(v > n) continue;
if(vis[v]) continue;
if(dist[1][u] + dist[0][v] + w == dist[1][S] || dist[0][u] + dist[1][v] + w == dist[1][S]){
g[2 * n + u].push_back({2 * n + v, 0});
q.push(v);
}
}
}
dij(V, dist[1]);
cout << dist[1][U + 3 * n];
}
# | 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... |