이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define int long long int
using namespace std;
const int maxn = 1e5 + 100, inf = 1e15 + 10;
int n ,m, S, T ,U ,V;
vector <pair <int ,int>> adj[maxn];
int dp[4][maxn] ,dist[2][maxn];
set<pair<int ,int>> s;
set<vector<int>> s2;
void djkasra(int num){
for(int i = 0 ;i < n; i++){
int v = (*s.begin()).second;
s.erase(s.begin());
for(auto [u ,w] : adj[v]){
if(dist[num][u] > dist[num][v] + w){
s.erase({dist[num][u], u});
dist[num][u] = dist[num][v] + w;
s.insert({dist[num][u], u});
}
}
if(s.size() == 0) break;
}
}
void daiikasra(){
while(s2.size() > 0){
vector<int> p = (*s2.begin());
int v = p[1];
int state = p[2];
s2.erase(s2.begin());
//s2 has first ==> distance / second.first ==> vertice / second.second ==> state
if(state == 0){
//here we are updating out dp of state 0
//dist[0][T] == minimum path between S and T
for(auto [u , w] : adj[v]){
//here we are checking edges that only belong to the shortest path DAG
if(dist[0][v] + dist[1][u] + w == dist[0][T]){
if(dp[1][u] > dp[state][v]){
dp[1][u] = dp[state][v];
s2.insert({dp[1][u], u, 1});
}
}
if(dist[1][v] + dist[0][u] + w == dist[0][T]){
if(dp[2][u] > dp[state][v]){
dp[2][u] = dp[state][v];
s2.insert({dp[2][u], u, 2});
}
}
}
for(auto [u , w] : adj[v]){
//we are updating a state the we dont use the DAG paths
if(dp[0][u] > dp[state][v] + w){
dp[0][u] = dp[state][v] + w;
s2.insert({dp[0][u], u ,0});
}
}
}
if(state == 1){
//state we are going the same direction as s to t in DAG
for(auto [u , w] : adj[v]){
//here we are checking edges that only belong to the shortest path DAG
if(dist[0][v] + dist[1][u] + w == dist[0][T]){
if(dp[1][u] > dp[state][v]){
dp[1][u] = dp[state][v];
s2.insert({dp[1][u], u, 1});
}
}
else{
if(dp[3][u] > dp[state][v] + w){
dp[3][u] = dp[state][v] + w;
s2.insert({dp[3][u], u, 3});
}
}
}
}
if(state == 2){
//state we are going the oppisite direction as s to t in DAG (t ==> s)
for(auto [u , w] : adj[v]){
//here we are checking edges that only belong to the shortest path DAG
if(dist[0][u] + dist[1][v] + w == dist[0][T]){
if(dp[2][u] > dp[state][v]){
dp[2][u] = dp[state][v];
s2.insert({dp[2][u], u, 2});
}
}
else{
if(dp[3][u] > dp[state][v] + w){
dp[3][u] = dp[state][v] + w;
s2.insert({dp[3][u], u, 3});
}
}
}
}
if(state == 3){
//state == 3 / state where we finish using the DAG of shortest path from s ==> t and we begin to go to V
for(auto [u , w] : adj[v]){
//here we are checking edges that only belong to the shortest path DAG
if(dp[3][u] > dp[state][v] + w){
dp[3][u] = dp[state][v] + w;
s2.insert({dp[3][u], u, 3});
}
}
}
}
}
int32_t main(){
ios::sync_with_stdio(0) , cout.tie(0) ,cin.tie(0);
cin >> n >> m >> S >> T >> U >> V;
for(int i = 0 ;i < m; i++){
int x ,y ,z;
cin >> x >> y >> z;
adj[x].push_back({y , z});
adj[y].push_back({x , z});
}
for(int i = 0; i <= n; i++){
dist[0][i] = inf;
}
dist[0][S] = 0;
for(int i = 1 ;i <= n; i++){
s.insert({dist[0][i], i});
}
djkasra(0);
for(int i = 0; i <= n; i++){
dist[1][i] = inf;
}
dist[1][T] = 0;
for(int i = 1 ;i <= n; i++){
s.insert({dist[1][i], i});
}
djkasra(1);
for(int j = 0 ;j < 4 ; j++){
for(int i = 0 ;i <= n; i++){
dp[j][i] = inf;
}
}
dp[0][U] = 0;
for(int i = 1 ; i <= n; i++){
s2.insert({dp[0][i],i ,0});
}
daiikasra();
cout << min({dp[0][V], dp[1][V] ,dp[2][V], dp[3][V]}) << endl;
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... |