#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <functional>
#include <cassert>
using namespace std;
#define int long long
int N, M;
int S, T;
int U, V;
#define Qnode priority_queue<Node, vector<Node>, greater<Node>>
#define Qnode_from priority_queue<NodeFrom, vector<NodeFrom>, greater<NodeFrom>>
vector<map<int, int>> G;
class NodeFrom{
public:
int cost, node, from;
const bool operator>(const NodeFrom& o) const{
return cost > o.cost;
}
const bool operator>=(const NodeFrom& o) const{
return cost >= o.cost;
}
const bool operator<=(const NodeFrom& o) const{
return cost <= o.cost;
}
const bool operator<(const NodeFrom& o) const{
return cost < o.cost;
}
};
class Node{
public:
int cost, node;
int used=false;
const bool operator>(const Node& o) const{
return cost > o.cost;
}
const bool operator>=(const Node& o) const{
return cost >= o.cost;
}
const bool operator<=(const Node& o) const{
return cost <= o.cost;
}
const bool operator<(const Node& o) const{
return cost < o.cost;
}
};
vector<bool> is_solut;
vector<bool> is_in_solut(vector<vector<int>> G, int node){
vector<bool> visited(N, false);
function<void(int)> dfs;
dfs = [&](int node){
if(visited[node])return;
visited[node] = true;
for(int next_node:G[node]){
if(next_node == -1)continue;
if(!visited[next_node])
dfs(next_node);
}
};
dfs(node);
return visited;
}
void add_recurs(Qnode* Q, vector<vector<int>>& G, int node, int cost, vector<bool>& visited){
for(int next_node:G[node]){
if(!visited[next_node*2+1] && is_solut[next_node]){
//visited[next_node*2+1] = true;
Node cur={cost, next_node, true};
Q->push(cur);
add_recurs(Q, G, next_node, cost, visited);
//visited[next_node*2+1] = false;
}
}
}
signed main(){
cin >> N >> M;
cin >> S >> T;
cin >> U >> V;
S--, U--, T--, V--;
G = vector<map<int, int>>(N);
for(int i=0; i<M; i++){
int node0, node1, cost;
cin >> node0 >> node1 >> cost;
node0--, node1--;
G[node0][node1] = cost;
G[node1][node0] = cost;
}
Qnode_from Q;
vector<int> S_T(N, -1);
vector<vector<int>> S_Tup(N);
vector<vector<int>> S_Tdown(N);
Q.push({0, S, -1});
size_t maxi_mem = 0;
while(!Q.empty()){
maxi_mem = max(maxi_mem, Q.size()*sizeof(NodeFrom));
//cout << Q.size()*sizeof(NodeFrom) << '\n';
NodeFrom cur=Q.top();
Q.pop();
//cout << cur.node << ' ' << cur.from << ' ' << cur.cost << '\n';
if(S_T[cur.node] != -1){
if(S_T[cur.node] == cur.cost && cur.from != -1){
S_Tup[cur.node].push_back(cur.from);
S_Tdown[cur.from].push_back(cur.node);
}
continue;
}
if(S_T[T] != -1 && cur.cost > S_T[T])break;
S_T[cur.node] = cur.cost;
if(cur.from != -1){
S_Tup[cur.node].push_back(cur.from);
S_Tdown[cur.from].push_back(cur.node);
}
for(auto A:G[cur.node]){
if(S_T[A.first] == -1)
Q.push({cur.cost+A.second, A.first, cur.node});
}
}
is_solut = is_in_solut(S_Tup, T);
vector<bool> U_V(N*4, false);
Qnode Q2;
Q2.push({0, U, false});
while(!Q2.empty()){
maxi_mem = max(maxi_mem, Q2.size()*sizeof(Node));
Node cur=Q2.top();
Q2.pop();
//cout << cur.node << ' ' << cur.cost << ' ' << cur.used << '\n';
int key = cur.node*4+cur.used;
if(cur.node == V){
cout << cur.cost << '\n';
break;
};
if(U_V[key])
continue;
U_V[key] = true;
int next_used = cur.used?3:0;
for(auto A:G[cur.node]){
if(!U_V[A.first*4+next_used])
Q2.push({cur.cost+A.second, A.first, next_used});
}
if(is_solut[cur.node]){
if(cur.used == 0 || cur.used == 1)
for(int next_node:S_Tup[cur.node])
if(is_solut[next_node] && !U_V[next_node*4+1])
Q2.push({cur.cost, next_node, 1});
if(cur.used == 0 || cur.used == 2)
for(int next_node:S_Tdown[cur.node])
if(is_solut[next_node] && !U_V[next_node*4+2])
Q2.push({cur.cost, next_node, 2});
}
}
//cout << maxi_mem << '\n';
}
# | 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... |