이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)
vector<vector<ll>> edges[100001];
unordered_set<ll> newedges[100001];
ll sdists[100001];
ll udists[100001];
ll vdists[100001];
ll visited[100001];
ll dp[2][100001];
vector<ll> topsort;
void dfs(ll a){
for (auto&i : edges[a]){
if (newedges[i[0]].count(a)) continue;
if (sdists[i[0]] == sdists[a] - i[1]){
newedges[i[0]].insert(a);
dfs(i[0]);
}
}
}
void dfs2(ll a){
for (auto&i : newedges[a]){
if (!visited[i]){
visited[i] = true;
dfs2(i);
}
}
topsort.push_back(a);
}
int main(){
ll n,m,s,t,u,v;
cin >> n >> m >> s >> t >> u >> v;
FOR(i,0,100001){
sdists[i] = LLONG_MAX / 2;
udists[i] = LLONG_MAX / 2;
vdists[i] = LLONG_MAX / 2;
}
FOR(i,0,m){
ll a,b,c;
cin >> a >> b >> c;
edges[a].push_back({b,c});
edges[b].push_back({a,c});
}
priority_queue<vector<ll>, vector<vector<ll>>, greater<vector<ll>>> pq;
FOR(i,0,100001) visited[i] = false;
visited[s] = true;
sdists[s] = 0;
pq.push({0,s});
while (pq.size()){
vector<ll> node = pq.top();
pq.pop();
if (node[0] != sdists[node[1]]) continue;
for (auto&i : edges[node[1]]){
if (sdists[i[0]] > sdists[node[1]] + i[1]){
sdists[i[0]] = sdists[node[1]] + i[1];
pq.push({sdists[i[0]],i[0]});
}
}
}
FOR(i,0,100001) visited[i] = false;
visited[t] = true;
dfs(t);
FOR(i,0,100001) visited[i] = false;
visited[u] = true;
udists[u] = 0;
pq.push({0,u});
while (pq.size()){
vector<ll> node = pq.top();
pq.pop();
if (node[0] != udists[node[1]]) continue;
for (auto&i : edges[node[1]]){
if (udists[i[0]] > udists[node[1]] + i[1]){
udists[i[0]] = udists[node[1]] + i[1];
pq.push({udists[i[0]],i[0]});
}
}
}
FOR(i,0,100001) visited[i] = false;
visited[v] = true;
vdists[v] = 0;
pq.push({0,v});
while (pq.size()){
vector<ll> node = pq.top();
pq.pop();
if (node[0] != vdists[node[1]]) continue;
for (auto&i : edges[node[1]]){
if (vdists[i[0]] > vdists[node[1]] + i[1]){
vdists[i[0]] = vdists[node[1]] + i[1];
pq.push({vdists[i[0]],i[0]});
}
}
}
FOR(i,0,100001) visited[i] = false;
FOR(i,1,n+1){
if (!visited[i] && newedges[i].size()){
visited[i] = true;
dfs2(i);
}
}
FOR(i,0,100001){
dp[0][i] = udists[i];
dp[1][i] = vdists[i];
}
reverse(topsort.begin(), topsort.end());
ll ans = LLONG_MAX / 2;
for (auto&i : topsort){
//cout << i << " " << dp[1][i] << " " << dp[0][i] << endl;
ans = min(ans, dp[1][i] + dp[0][i]);
for (auto&j : newedges[i]){
dp[1][j] = min(dp[1][j], dp[1][i]);
ans = min(ans, dp[1][j] + dp[0][j]);
}
}
FOR(i,0,100001){
dp[0][i] = udists[i];
dp[1][i] = vdists[i];
}
for (auto&i : topsort){
//cout << i << " " << dp[1][i] << " " << dp[0][i] << endl;
ans = min(ans, dp[1][i] + dp[0][i]);
for (auto&j : newedges[i]){
dp[0][j] = min(dp[0][j], dp[0][i]);
ans = min(ans, dp[1][j] + dp[0][j]);
}
}
ans = min(ans, vdists[u]);
cout << ans << 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... |