이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FOR(x, a, b) for(int x=a;x < int(b); x++)
#define endl '\n'
#define TESTCASE ll t; cin >> t; for(ll T=0; T < t; T++)
using namespace std;
// using namespace __gnu_pbds;
typedef unsigned long long int ull;
typedef long long int ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<short> vs;
typedef long double ld;
// template <class T>
// using Tree =
// tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll INF = ll(1e18) + 10;
const ll INIT = 7;
const ll MAX_VAL = 5000;
const ll MAX_SZ = (ll) 1e4;
const ll MAX_N = 1e5;
const long double eps = 1e-4;
const ll MOD = ll(1e9) + 7;
vi rd = {0, 1 , 0, -1}, cd = {1, 0, -1, 0};
ll add(ll a, ll b) {
return ((a % MOD) + (b % MOD) + 2ll * MOD) % MOD;
}
ll mult(ll a, ll b) {
return (((a % MOD) * (b % MOD)) + MOD) % MOD;
}
ll lcm(ll a, ll b) {
return (a * b) / gcd(a, b);
}
ll dp[MAX_N + 1], ssp[MAX_N + 1], usp[MAX_N + 1], vsp[MAX_N + 1];
int khans[MAX_N + 1];
vpi adj[MAX_N + 1];
vector<vi> graph1(MAX_N + 1), graph2(MAX_N + 1), graph3(MAX_N + 1);
int n, m, s, t, u, v;
void djk(ll* sp, int strt, bool use_graph) {
priority_queue<pair<ll, pi>, vector<pair<ll, pi>>, greater<pair<ll, pi>>> pq;
pq.push(make_pair(0, make_pair(strt, 0)));
while(!pq.empty()) {
auto [cost, nodes] = pq.top();
auto [cur_node, prev_node] = nodes;
pq.pop();
if(use_graph && (sp[cur_node] == cost || !sp[cur_node]) && cur_node != strt) {
graph1[cur_node].push_back(prev_node);
}
if((cur_node != strt && sp[cur_node]) || (cur_node == strt && cost)) continue;
sp[cur_node] = cost;
for(auto [next_cost, next_node] : adj[cur_node]) {
pq.push(make_pair(cost + next_cost, make_pair(next_node, cur_node)));
}
}
}
ll solve(vector<vi>& graph, ll strt) {
memset(khans, 0, sizeof(int) * (n + 1));
FOR(i, 1, n + 1) {
for(auto node : graph[i]) khans[node]++;
dp[i] = usp[i];
}
ll ans = INF;
queue<int> khans_list;
khans_list.push(strt);
while(khans_list.size()) {
int cur = khans_list.front();
khans_list.pop();
ans = min(ans, dp[cur] + vsp[cur]);
// cout << cur << " : " << dp[cur] << " " << vsp[cur] << endl;
for(auto next : graph[cur]) {
khans[next]--;
dp[next] = min(dp[next], dp[cur]);
if(!khans[next]) khans_list.push(next);
}
}
// FOR(i, 1, n + 1) cout << dp[i] << " ";
// cout << endl;
return ans;
}
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
fast
// TESTCASE {
// }
cin >> n >> m >> s >> t >> u >> v;
FOR(i, 0, m) {
int a, b, c;
cin >> a >> b >> c;
adj[a].push_back(make_pair(c, b));
adj[b].push_back(make_pair(c, a));
}
djk(usp, u, false);
djk(vsp, v, false);
djk(ssp, s, true);
queue<int> tr;
tr.push(t);
while(tr.size()) {
int cur = tr.front();
tr.pop();
for(auto next : graph1[cur]) {
if(!graph2[next].size()) tr.push(next);
graph2[next].push_back(cur);
graph3[cur].push_back(next);
}
// cout << cur << " " ;
}
// cout << endl;
cout << min(min(solve(graph3, t), solve(graph2, s)), usp[v]) << endl;
// FOR(i, 1, n + 1) {
// cout << i << ": ";
// for(auto x : graph1[i]) cout << x << " ";
// cout << endl;
// }
// FOR(i, 1, n + 1) cout << ssp[i] << " ";
// cout << endl;
// FOR(i, 1, n + 1) cout << usp[i] << " ";
// cout << endl;
// FOR(i, 1, n + 1) cout << vsp[i] << " ";
// cout << 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... |