이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
#define INF 1e18
using namespace std;
typedef pair<ll,ll> pii;
const int maxn = 1e5 + 1;
int n,m,S,T,U,V;
ll dist[2][maxn], dp[2][maxn], d[maxn];
vector<pii> adj[maxn];
void dijsktra1(int id, int s) {
for (int i = 1; i <= n; i++) {
dist[id][i] = INF;
}
dist[id][s] = 0;
priority_queue<pii, vector<pii>, greater<pii> > pq;
pq.push(pii(0,s));
while (!pq.empty()) {
ll u = pq.top().second, D = pq.top().first;
pq.pop();
if (D > dist[id][u]) continue;
for (pii i: adj[u]) {
int v = i.first;
ll w = i.second;
if (D+w < dist[id][v]) {
dist[id][v] = D + w;
pq.push(pii(dist[id][v],v));
}
}
}
}
ll dijsktra2(int s, int f) {
for (int i = 0; i <= n; i++) {
d[i] = dp[0][i] = dp[1][i] = INF;
}
d[s] = 0;
priority_queue<pii, vector<pii>, greater<pii> > pq;
pq.push(pii(0,s));
dp[0][s] = dist[0][s];
dp[1][s] = dist[1][s];
while (!pq.empty()) {
ll u = pq.top().second, D = pq.top().first;
pq.pop();
if (D > d[u]) continue;
for (pii i: adj[u]) {
int v = i.first;
ll w = i.second;
if (D+w == d[v] && min(dp[0][u],dist[0][v]) + min(dp[1][u],dist[1][v]) <= dp[0][v] + dp[1][v]) {
dp[0][v] = min(dp[0][u],dist[0][v]);
dp[1][v] = min(dp[1][u],dist[1][v]);
} else if (D+w < d[v]) {
dp[0][v] = min(dp[0][u],dist[0][v]);
dp[1][v] = min(dp[1][u],dist[1][v]);
d[v] = D + w;
pq.push(pii(d[v],v));
}
}
}
return dp[0][f] + dp[1][f];
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m >> S >> T >> U >> V;
for (int i = 1; i <= m; i++) {
int u,v,w;
cin >> u >> v >> w;
adj[u].push_back(pii(v,w));
adj[v].push_back(pii(u,w));
}
dijsktra1(0,U);
dijsktra1(1,V);
ll res = dist[0][V];
res = min(res,dijsktra2(S,T));
res = min(res,dijsktra2(T,S));
cout << res;
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... |