이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
// author: aykhn
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define mpr make_pair
#define eb emplace_back
#define pb push_back
#define ts to_string
#define fi first
#define se second
#define ins insert
#define int ll
#define inf 0x3F3F3F3F
#define infll 0x3F3F3F3F3F3F3F3FLL
#define bpc __builtin_popcount
const int MXN = 1e5 + 5;
int dist[2][MXN];
int d[MXN];
int mn1[MXN], mn2[MXN];
vector<array<int, 2>> adj[MXN];
vector<int> par[MXN];
vector<int> g[MXN], o;
int used[MXN];
void dijk(int s, int id)
{
for (int i = 0; i < MXN; i++) dist[id][i] = infll;
priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>> pq;
dist[id][s] = 0;
pq.push({0, s});
while (!pq.empty())
{
array<int, 2> f = pq.top();
pq.pop();
if (f[0] > dist[id][f[1]]) continue;
for (const array<int, 2> &v : adj[f[1]])
{
if (dist[id][v[0]] > f[0] + v[1])
{
dist[id][v[0]] = f[0] + v[1];
pq.push({dist[id][v[0]], v[0]});
}
}
}
}
void dfs(int a)
{
used[a] = 1;
for (int v : par[a])
{
g[v].pb(a);
if (used[v]) continue;
dfs(v);
}
}
void dfs1(int a)
{
used[a] = 1;
for (int v : g[a])
{
if (used[v]) continue;
dfs1(v);
}
o.pb(a);
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
int n, m, s, t, u, v;
cin >> n >> m >> s >> t >> u >> v;
while (m--)
{
int u, v, w;
cin >> u >> v >> w;
adj[u].pb({v, w});
adj[v].pb({u, w});
}
dijk(u, 0);
dijk(v, 1);
for (int i = 0; i < MXN; i++) d[i] = mn1[i] = mn2[i] = infll;
priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>> pq;
d[s] = 0;
pq.push({0, s});
while (!pq.empty())
{
int f = pq.top()[1];
int w = pq.top()[0];
pq.pop();
if (w > d[f]) continue;
for (const array<int, 2> &v : adj[f])
{
if (d[v[0]] > w + v[1])
{
d[v[0]] = w + v[1];
par[v[0]].clear();
par[v[0]].pb(f);
pq.push({d[v[0]], v[0]});
}
else if (d[v[0]] == w + v[1]) par[v[0]].pb(f);
}
}
for (int i = 0; i < MXN; i++) used[i] = 0;
dfs(t);
for (int i = 0; i < MXN; i++) used[i] = 0;
dfs1(s);
reverse(all(o));
int res = infll;
for (int x : o)
{
mn1[x] = min(mn1[x], dist[0][x]);
mn2[x] = min(mn2[x], dist[1][x]);
res = min(res, mn1[x] + dist[1][x]);
res = min(res, mn2[x] + dist[0][x]);
for (int v : g[x])
{
mn1[v] = min(mn1[v], mn1[x]);
mn2[v] = min(mn2[v], mn2[x]);
}
}
cout << min(dist[0][v], res) << '\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... |