Submission #1192548

#TimeUsernameProblemLanguageResultExecution timeMemory
1192548jbn8Commuter Pass (JOI18_commuter_pass)C++20
15 / 100
591 ms327680 KiB
#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; bool used=false; 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; bool 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}); while(!Q.empty()){ 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*2, false); Qnode Q2; Q2.push({0, U, false}); while(!Q2.empty()){ Node cur=Q2.top(); Q2.pop(); //cout << cur.node << ' ' << cur.cost << ' ' << cur.used << '\n'; int key = cur.node*2+cur.used; if(cur.node == V){ cout << cur.cost << '\n'; break; }; if(U_V[key]) continue; U_V[key] = true; for(auto A:G[cur.node]){ if(!U_V[A.first*2+cur.used]) Q2.push({cur.cost+A.second, A.first, cur.used}); } if(!cur.used && is_solut[cur.node]){ add_recurs(&Q2, S_Tup, cur.node, cur.cost, U_V); add_recurs(&Q2, S_Tdown, cur.node, cur.cost, U_V); } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...