이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#ifdef lisie_bimbi
#else
#define endl '\n'
#endif
typedef long long ll;
const ll inf = 1'000'000'000'000'000'000;
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,bmi2,fma,popcnt")
//#define int long long
struct reb{
int a;
int b;
ll c;
};
vector<ll> dij(vector<vector<pair<int, ll>>> v, int start){
int n = v.size();
vector<ll> d(n, inf);
d[start] = 0;
set<pair<ll, int>> s;
for(int i = 0; i < n; i++){
s.insert({d[i], i});
}
while(!s.empty()){
auto [dist, u] = *s.begin();
s.erase(s.begin());
for(auto [i, j] : v[u]){
if(dist + j < d[i]){
s.erase({d[i], i});
d[i] = dist + j;
s.insert({d[i], i});
}
}
}
return d;
}
void solve(){
int n, m;
cin >> n >> m;
int s, t;
cin >> s >> t;
int s1, t1;
cin >> s1 >> t1;
s--;t--;s1--;t1--;
vector<reb> r;
vector<vector<pair<int, ll>>> v(n);
for(int i = 0; i < m; i++){
int a, b, c;
cin >> a >> b >> c;
a--;b--;
r.push_back({a, b, c});
v[a].emplace_back(b, c);
v[b].emplace_back(a, c);
}
auto ds = dij(v, s);
auto dt = dij(v, t);
vector<vector<pair<int, ll>>> v1(3 * n), v2(3 * n);
for(auto [a, b, c] : r){
if(ds[a] + c + dt[b] == ds[t]){
v1[n + a].emplace_back(n + b, 0);
v2[n + b].emplace_back(n + a, 0);
}
if(ds[b] + c + dt[a] == ds[t]){
v1[n + b].emplace_back(n + a, 0);
v2[n + a].emplace_back(n + b, 0);
}
v1[a].emplace_back(b, c);
v1[b].emplace_back(a, c);
v1[2 * n + a].emplace_back(2 * n + b, c);
v1[2 * n + b].emplace_back(2 * n + a, c);
v2[a].emplace_back(b, c);
v2[b].emplace_back(a, c);
v2[2 * n + a].emplace_back(2 * n + b, c);
v2[2 * n + b].emplace_back(2 * n + a, c);
}
for(int i = 0; i < n; i++){
v1[i].emplace_back(i + n, 0);
v1[i + n].emplace_back(i + 2 * n, 0);
v2[i].emplace_back(i + n, 0);
v2[i + n].emplace_back(i + 2 * n, 0);
}
auto d = dij(v1, s1);
auto d1 = dij(v2, s1);
cout << min(d[t1 + 2 * n], d1[t1 + 2 * n]) << endl;
}
signed main(){
#ifdef lisie_bimbi
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
cin.tie(nullptr)->sync_with_stdio(false);
#endif
cout << setprecision(5) << fixed;
int _ = 1;
//cin >> t;
while(_--){
solve();
}
return 0;
}
# | 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... |