이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
#include <map>
#include <set>
#include <complex>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <random>
#define ft first
#define sc second
#define pb push_back
#define len(v) (int)v.size()
#define int ll
using namespace std;
typedef long long ll;
int inf = 1e18 + 100;
struct edge {
int u, w, num;
edge(int _u, int _w, int _num) : u(_u), w(_w), num(_num) {}
};
vector<vector<edge>> g;
vector<int> djkstra(int n, int st) {
vector<int> d(n, inf);
d[st] = 0;
set<pair<int, int>> now;
now.insert({0, st});
while(len(now) > 0) {
auto rasm = *now.begin();
now.erase(rasm);
for (auto x : g[rasm.sc]) {
if(d[x.u] <= rasm.ft + x.w)
continue;
now.erase({d[x.u], x.u});
d[x.u] = rasm.ft + x.w;
now.insert({d[x.u], x.u});
}
}
return d;
}
signed main() {
#ifdef PC
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m, st, fn, st2, fn2;
cin >> n >> m;
cin >> st >> fn >> st2 >> fn2;
st--, fn--, st2--, fn2--;
g = vector<vector<edge>> (n);
vector<bool> good(m, 0);
vector<pair<pair<int, int>, int>> have;
for (int i = 0; i < m; i++) {
int a, b, w;
cin >> a >> b >> w;
a--, b--;
g[a].pb({b, w, i});
g[b].pb({a, w, i});
have.pb({{a, b}, w});
}
auto dst_st = djkstra(n, st);
auto dst_fn = djkstra(n, fn);
int min_dst = dst_st[fn];
// cout << min_dst << endl;
for (int i = 0; i < m; i++) {
if(dst_st[have[i].ft.ft] + dst_fn[have[i].ft.sc] + have[i].sc == min_dst)
good[i] = 1;
if(dst_fn[have[i].ft.ft] + dst_st[have[i].ft.sc] + have[i].sc == min_dst)
good[i] = 1;
// cout << i << " " << good[i] << endl;
}
map<pair<int, int>, int> d;
for (int i = 0; i < n; i++) {
d[{i, 0}] = d[{i, 1}] = d[{i, 2}] = d[{i, 3}] = inf;
}
d[{st2, 0}] = 0;
set<pair<int, pair<int, int>>> q;
q.insert({0, {st2, 0}});
while(len(q) > 0) {
auto rasm = *q.begin();
// cout << rasm.sc.ft << " " << rasm.sc.sc << " " << rasm.ft << endl;
q.erase(rasm);
if(rasm.sc.sc == 0) {
for (int j = 1; j < 4; j++) {
if(d[{rasm.sc.ft, j}] > rasm.ft) {
q.erase({d[{rasm.sc.ft, j}], {rasm.sc.ft, j}});
d[{rasm.sc.ft, j}] = rasm.ft;
q.insert({d[{rasm.sc.ft, j}], {rasm.sc.ft, j}});
}
}
}
if(rasm.sc.sc == 1 || rasm.sc.sc == 2) {
if(d[{rasm.sc.ft, 3}] > rasm.ft) {
q.erase({d[{rasm.sc.ft, 3}], {rasm.sc.ft, 3}});
d[{rasm.sc.ft, 3}] = rasm.ft;
q.insert({d[{rasm.sc.ft, 3}], {rasm.sc.ft, 3}});
}
}
for (auto x : g[rasm.sc.ft]) {
if(rasm.sc.sc == 1) {
if(!good[x.num])
continue;
if(dst_st[x.u] > dst_st[rasm.sc.ft])
continue;
if(d[{x.u, 1}] > rasm.ft) {
q.erase({d[{x.u, 1}], {x.u, 1}});
d[{x.u, 1}] = rasm.ft;
q.insert({d[{x.u, 1}], {x.u, 1}});
}
continue;
}
if(rasm.sc.sc == 2) {
if(!good[x.num])
continue;
if(dst_st[x.u] < dst_st[rasm.sc.ft])
continue;
if(d[{x.u, 2}] > rasm.ft) {
q.erase({d[{x.u, 2}], {x.u, 2}});
d[{x.u, 2}] = rasm.ft;
q.insert({d[{x.u, 2}], {x.u, 2}});
}
continue;
}
if(d[{x.u, rasm.sc.sc}] > rasm.ft + x.w) {
q.erase({d[{x.u, rasm.sc.sc}], {x.u, rasm.sc.sc}});
d[{x.u, rasm.sc.sc}] = rasm.ft + x.w;
q.insert({d[{x.u, rasm.sc.sc}], {x.u, rasm.sc.sc}});
}
}
}
cout << d[{fn2, 3}] << 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... |