이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;
#define FOR(i, j, k) for (ll i = j; i < (ll) k; ++i)
#define FORD(i, j, k) for (ll i = j; i >= (ll) k; --i)
#define nl "\n"
#define sp " "
#define all(x) (x).begin(), (x).end()
#define sc second
#define fr first
#define pb emplace_back
struct edge {
ll b, w;
ll id;
};
const ll mxN = 1e5 + 5;
ll n, m;
vector<edge> adj[mxN];
vi distU, distV;
vi djik(ll x) {
vi dist(n + 1, 1e15);
bool vis[n + 1] = {};
priority_queue<pi> pq;
dist[x] = 0;
pq.emplace(0, x);
while(!pq.empty()) {
ll u = pq.top().sc;
pq.pop();
if(vis[u]) continue;
vis[u] = true;
for(auto [v, w, id] : adj[u]) {
if(dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.emplace(-dist[v], v);
}
}
}
return dist;
}
ll solve(ll x, ll y) {
ll dpU[n + 1], dpV[n + 1];
fill(dpU, dpU + n + 1, 1e15);
fill(dpV, dpV + n + 1, 1e15);
vi dist(n + 1, 1e15);
ll from[n + 1] = {};
bool vis[n + 1] = {};
priority_queue<pi> pq;
dist[x] = 0;
from[x] = 0;
pq.emplace(0, x);
while(!pq.empty()) {
ll u = pq.top().sc;
ll d = -pq.top().fr;
pq.pop();
if(!vis[u]) {
vis[u] = true;
dpU[u] = min(distU[u], dpU[from[u]]);
dpV[u] = min(distV[u], dpV[from[u]]);
for(auto [v, w, id] : adj[u]) {
if(dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
from[v] = u;
pq.emplace(-dist[v], v);
}
}
} else if(d == dist[u]) {
if(min(distU[u], dpU[from[u]]) + min(distV[u], dpV[from[u]]) <= dpU[u] + dpV[u]) {
dpU[u] = min(distU[u], dpU[from[u]]);
dpV[u] = min(distV[u], dpV[from[u]]);
}
}
}
return dpU[y] + dpV[y];
}
void solve()
{
cin >> n >> m;
ll s, t;
cin >> s >> t;
ll u, v;
cin >> u >> v;
FOR(i, 0, m) {
ll a, b, c;
cin >> a >> b >> c;
edge curr;
curr.b = b;
curr.w = c;
curr.id = i;
adj[a].pb(curr);
curr.b = a;
adj[b].pb(curr);
}
distU = djik(u);
distV = djik(v);
ll ans = distU[v];
ans = min(ans, solve(s, t));
ans = min(ans, solve(t, s));
cout << ans << nl;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t = 1;
// cin >> t;
while (t--)
{
solve();
}
}
# | 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... |