이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define sz(x) (int)(x.size())
#define itr(x) x.begin(), x.end()
#ifdef LOC
#define prv(x) cerr << #x << " : "; for(auto& ov : x) cout << ov << " "; cout << "\n";
#define debug(...) cerr << #__VA_ARGS__ << " : "; for(auto& dval : {__VA_ARGS__}) cerr << dval << " "; cerr << "\n";
#else
#define debug(...)
#define prv(x)
#define LOC 0
#endif
void dijkstra(int s, vector<vector<array<ll,2>>>& adj, vector<ll>& dis) {
priority_queue<array<ll,2>> que;
que.push({0, s});
while(sz(que)) {
ll idx = que.top()[1], d = -que.top()[0];
que.pop();
if(dis[idx] <= d) {
continue;
}
dis[idx] = d;
for(auto& e : adj[idx]) {
que.push({-(d + e[1]), e[0]});
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
if(LOC) {
cerr << "debug mode\n";
}
int n, m, s, t, u, v;
cin >> n >> m >> s >> t >> u >> v;
s--; t--; u--; v--;
vector<array<ll,3>> edges(m);
for(auto& e : edges) {
cin >> e[0] >> e[1] >> e[2];
e[0]--; e[1]--;
}
vector<vector<array<ll,2>>> G(n);
for(auto& e : edges) {
G[e[0]].pb({e[1], e[2]});
G[e[1]].pb({e[0], e[2]});
}
vector<ll> sd(n, INT64_MAX), td(n, INT64_MAX), ud(n, INT64_MAX), vd(n, INT64_MAX);
dijkstra(s, G, sd);
dijkstra(t, G, td);
dijkstra(u, G, ud);
dijkstra(v, G, vd);
vector<int> in(n, 0);
vector<vector<int>> dag(n);
for(auto& e : edges) {
if(sd[e[0]] + e[2] + td[e[1]] == td[s]) {
dag[e[0]].pb(e[1]);
in[e[1]]++;
}
if(sd[e[1]] + e[2] + td[e[0]] == td[s]) {
dag[e[1]].pb(e[0]);
in[e[0]]++;
}
}
vector<int> que;
vector<ll> mnud(n, INT64_MAX / 2), mnvd(n, INT64_MAX / 2);
for(int i = 0; i < n; i++) {
if(in[i] == 0) {
que.pb(i);
}
}
ll ans = sd[t];
while(sz(que) > 0) {
int idx = que.back();
que.pop_back();
mnud[idx] = min(mnud[idx], ud[idx]);
// mnvd[idx] = min(mnvd[idx], vd[idx]);
ans = min(ans, mnud[idx] + vd[idx]);
// ans = min(ans, mnvd[idx] + ud[idx]);
for(int e : dag[idx]) {
mnud[e] = min(mnud[e], mnud[idx]);
// mnvd[e] = min(mnvd[e], mnvd[idx]);
in[e]--;
if(in[e] == 0) {
que.pb(e);
}
}
}
cout << ans << "\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... |