이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//
// ~oisín~ C++ Template
//
#include <bits/stdc++.h>
#define MX_N 200005
#define mp make_pair
#define mod7 1000000007
#define modpi 314159
#define PI 3.141592653589793238
#define pb push_back
#define FastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define All(a) a.begin(),a.end()
#define fi first
#define se second
#define ll long long int
#define ull unsigned long long int
int kx[8] = {+2, +2, -2, -2, +1, +1, -1, -1};
int ky[8] = {+1, -1, +1, -1, +2, -2, +2, -2};
int d9x[9] = {+1, +1, +1, +0, +0, +0, -1, -1, -1};
int d9y[9] = {+1, +0, -1, +1, +0, -1, +1, +0, -1};
int dx4[4] = {+0, +0, +1, -1};
int dy4[4] = {+1, -1, +0, +0};
ll gcd(ull a, ull b){
return (a==0)?b:gcd(b%a,a);
}
ll lcm(ull a, ull b){
return a*(b/gcd(a,b));
}
const long long INF = 1e18;
using namespace std;
int N, M, S, T, U, V;
bool vis[MX_N];
bool topovis[MX_N];
vector<int> toposort;
ll dist[MX_N][3];
ll mass[MX_N];
vector<pair<int, int> > adj[MX_N];
vector<int> dag_adj[MX_N];
ll dpU[MX_N], dpV[MX_N];
void topodfs(int at){
topovis[at] = true;
for(int to : dag_adj[at]){
if(!topovis[to]){
topodfs(to);
}
}
toposort.pb(at);
return;
}
int main(){
cin >> N >> M >> S >> T >> U >> V;
--S, --T, --U, --V;
for(int i=0;i<M;++i){
int u, v;
cin >> u >> v >> mass[i];
--u, --v;
adj[u].pb({v, i});
adj[v].pb({u, i});
}
for(int i=0;i<N;++i){
dist[i][0] = dist[i][1] = dist[i][2] = INF;
}
priority_queue<pair<ll, int> > pq;
dist[S][0] = 0ll;
pq.push({0, S});
while(!pq.empty()){
auto [d, at] = pq.top();
pq.pop();
d *= -1ll;
if(d != dist[at][0]){
continue;
}
for(auto& [to, id] : adj[at]){
if(dist[to][0] > dist[at][0] + mass[id]){
dist[to][0] = dist[at][0] + mass[id];
pq.push({-1ll*dist[to][0], to});
}
}
}
dist[U][1] = 0ll;
pq.push({0, U});
while(!pq.empty()){
auto [d, at] = pq.top();
pq.pop();
d *= -1ll;
if(d != dist[at][1]){
continue;
}
for(auto& [to, id] : adj[at]){
if(dist[to][1] > dist[at][1] + mass[id]){
dist[to][1] = dist[at][1] + mass[id];
pq.push({-1ll*dist[to][1], to});
}
}
}
dist[V][2] = 0ll;
pq.push({0, V});
while(!pq.empty()){
auto [d, at] = pq.top();
pq.pop();
d *= -1ll;
if(d != dist[at][2]){
continue;
}
for(auto& [to, id] : adj[at]){
if(dist[to][2] > dist[at][2] + mass[id]){
dist[to][2] = dist[at][2] + mass[id];
pq.push({-1ll*dist[to][2], to});
}
}
}
memset(vis, 0, sizeof(vis));
vis[T] = true;
queue<int> Q;
Q.push(T);
while(!Q.empty()){
int at = Q.front();
Q.pop();
for(auto& [to, id] : adj[at]){
if(dist[to][0] + mass[id] == dist[at][0]){
dag_adj[to].pb(at);
if(!vis[to]){
vis[to] = true;
Q.push(to);
}
}
}
}
for(int i=0;i<N;++i){
dpU[i] = dist[i][1];
dpV[i] = dist[i][2];
}
memset(topovis, 0, sizeof(topovis));
topodfs(S);
reverse(All(toposort));
ll ans = dist[V][0];
for(int at : toposort){
for(int to : dag_adj[at]){
dpU[to] = min(dpU[to], dpU[at]);
dpV[to] = min(dpV[to], dpV[at]);
}
ans = min(ans, dpU[at] + dpV[at]);
}
// for(int i=0;i<N;++i){
// cout << i+1 << " : dpU & dpV = " << dpU[i] << " & " << dpV[i] << endl;
// }
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... |