이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
const int MOD = 1e9+7;
#define F first
#define S second
#define PB push_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
void FASTIO() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }
const int MXN = 1e5+5;
const ll INF = 1e15;
int n, m;
int s, t, u, v;
vector<pii> adj[MXN];
vector<pii> dag[MXN]; // s -> t
ll dist_s[MXN], dist_t[MXN];
ll dist_u[MXN], dist_v[MXN];
void dijkstra(int start, ll dist[]) {
priority_queue<pli, vector<pli>, greater<pli>> PQ;
fill(dist, dist+n+1, INF);
dist[start] = 0;
PQ.push({0, start});
while(!PQ.empty()) {
ll d = PQ.top().F;
int i = PQ.top().S;
PQ.pop();
if(d != dist[i]) continue;
for(auto e : adj[i]) {
if(dist[e.F] > d+e.S) {
dist[e.F] = d+e.S;
PQ.push({dist[e.F], e.F});
}
}
}
}
bool visited[MXN];
pll mn[MXN]; // first - min dist to v, second - min dist to u
ll ans = INF;
void recur(int i) {
if(visited[i]) return;
visited[i] = true;
mn[i].F = dist_v[i];
mn[i].S = dist_u[i];
for(auto e : dag[i]) {
recur(e.F);
mn[i].F = min(mn[i].F, mn[e.F].F);
mn[i].S = min(mn[i].S, mn[e.F].S);
}
ans = min(ans, dist_u[i]+mn[i].F);
ans = min(ans, dist_v[i]+mn[i].S);
}
int main() {
FASTIO();
cin >> n >> m;
cin >> s >> t;
cin >> u >> v;
for(int i = 0; i < m; i++) {
int a, b, c; cin >> a >> b >> c;
adj[a].PB({b, c});
adj[b].PB({a, c});
}
dijkstra(s, dist_s);
dijkstra(t, dist_t);
dijkstra(u, dist_u);
dijkstra(v, dist_v);
for(int i = 1; i <= n; i++) {
for(auto e : adj[i]) {
if(dist_s[i]+dist_t[e.F]+e.S == dist_s[t]) {
dag[i].PB(e);
}
}
}
ans = dist_u[v];
for(int i = 1; i <= n; i++) {
if(!dag[i].empty()) {
recur(i);
}
}
cout << ans << "\n";
return 0;
}
/*
6 6
1 5
4 6
1 2 1
2 3 1
3 5 1
2 4 2
4 5 3
5 6 1
ans: 3
7 9
1 5
4 6
7 2 1
7 3 1
7 5 1
1 2 1
2 3 1
3 5 1
2 4 2
4 5 3
5 6 1
ans: 3
5 5
1 3
4 5
1 2 1
2 3 1
1 3 2
1 4 3
2 5 3
ans: 6
5 6
1 3
4 5
1 2 1
2 3 1
1 3 2
1 4 3
2 5 3
3 5 1
ans: 4
*/
# | 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... |