| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 654603 | leroycut | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18 + 3;
const int N = 1e5 + 3;
class cmt
{
public:
bool operator() (pair<int, ll> a, pair<int, ll> b){
return a.second > b.second;
}
};
int s, t, v, u, n, m;
vector<pair<int, ll>> g[N];
vector<int> dag1[N], dag2[N];
ll dpv[N], dpu[N];
vector<ll> ds, dv, du;
vector<ll> djikstra(int S){
vector<ll> d(N, INF);
d[S] = 0;
priority_queue<pair<int, ll>, vector<pair<int, ll>>, cmt> q;
q.push({S, 0});
while(!q.empty()){
auto cur = q.top();
q.pop();
int node = cur.first;
ll dist = cur.second;
if(dist != d[node]) continue;
for(auto i : g[node]){
if(dist + i.second < d[i.first]){
d[i.first] = dist + i.second;
q.push({i.first, dist + i.second});
}
}
}
return d;
}
void dfs(int S){
for(auto i : g[S]){
if(ds[i.first] < ds[S]){
if(ds[S] - i.second == ds[i.first]){
dag1[S].push_back(i.first);
dag2[i.first].push_back(S);
dfs(i.first);
}
}
}
}
ll ans = INF;
void dfsp1(int S){
dpu[S] = min(dpu[S], du[S]);
dpv[S] = min(dpv[S], dv[S]);
for(auto i : dag1[S]){
dfsp1(i);
dpu[S] = min(dpu[i], dpu[S]);
dpv[S] = min(dpv[i], dpv[S]);
}
ans = min(ans, dv[S] + dpu[S]);
ans = min(ans, du[S] + dpv[S]);
}
void dfsp2(int S){
dpu[S] = min(dpu[S], du[S]);
dpv[S] = min(dpv[S], dv[S]);
for(auto i : dag2[S]){
dfsp2(i);
dpu[S] = min(dpu[i], dpu[S]);
dpv[S] = min(dpv[i], dpv[S]);
}
ans = min(ans, dv[S] + dpu[S]);
ans = min(ans, du[S] + dpv[S]);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
for(int i = 0; i < N; ++i){
dpu[i] = dpv[i] = INF;
}
cin >> n >> m >> s >> t >> v >> u;
for(int i = 0; i < m; ++i){
int a, b;
ll c;
cin >> a >> b >> c;
g[a].push_back({b, c});
g[b].push_back({a, c});
}
ds = djikstra(s);
du = djikstra(u);
dv = djikstra(v);
dfs(t);
dfsp1(t);
for(int i = 0; i < N; ++i){
dpu[i] = dpv[i] = INF;
}
dfsp2(s);
cout << min(ans, dv[u]);
}