이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <math.h>
#include <tuple>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <map>
#include <climits>
#include <fstream>
using namespace std;
typedef long long ll;
#define all(v) v.begin(). v.end()
vector < vector<tuple<ll, ll>>> adj; // [node from], [i] -> {node to, cost}
ll du[100001], dv[100001], ds[100001], dpU[100001], dpV[100001];
ll ans;
void dijkstra1(ll s, ll dist[]) {
priority_queue<tuple<ll, ll>, vector<tuple<ll, ll>>, greater<tuple<ll, ll>>> pq;
fill(dist, dist + 100001, LLONG_MAX);
pq.push({ 0, s });
dist[s] = 0;
while (!pq.empty()) {
ll a, d; tie(d, a) = pq.top(); pq.pop();
if (dist[a] != d) continue;
for (auto i : adj[a]) {
ll b, c; tie(b, c) = i;
if (dist[b] > dist[a] + c) {
dist[b] = dist[a] + c;
pq.push({ dist[b], b });
}
}
}
}
void dijkstra2(ll s, ll e) {
priority_queue<tuple<ll, ll>, vector<tuple<ll, ll>>, greater<tuple<ll, ll>>> pq;
fill(dpV, dpV + 100001, LLONG_MAX);
fill(dpU, dpU + 100001, LLONG_MAX);
fill(ds, ds + 100001, LLONG_MAX);
pq.push({ 0, s });
ds[s] = 0;
dpV[s] = dv[s];
dpU[s] = du[s];
while (!pq.empty()) {
ll d, a; tie(d, a) = pq.top(); pq.pop();
if (ds[a] != d) continue;
for (auto i : adj[a]) {
ll b, c; tie(b, c) = i;
if (ds[b] > ds[a] + c) {
dpV[b] = min(dpV[a], dv[b]);
dpU[b] = min(dpU[a], du[b]);
ds[b] = ds[a] + c;
pq.push({ ds[b], b });
}
else if (ds[b] == ds[a] + c && min(dpU[a], du[b]) + min(dpV[a], dv[b]) <= dpV[b] + dpU[b]) {
dpV[b] = min(dpV[a], dv[b]);
dpU[b] = min(dpU[a], du[b]);
}
}
}
ans = min(ans, dpV[e] + dpU[e]);
}
int main()
{
ll n, m; cin >> n >> m;
ll s, t; cin >> s >> t;
ll u, v; cin >> u >> v;
adj.resize(n+1);
for (ll i = 0; i < m; i++)
{
ll a, b, c; cin >> a >> b >> c;
adj[a].push_back({ b, c });
adj[b].push_back({ a, c });
}
dijkstra1(u, du);
dijkstra1(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... |