Submission #1192393

#TimeUsernameProblemLanguageResultExecution timeMemory
1192393jbn8Commuter Pass (JOI18_commuter_pass)C++20
0 / 100
2095 ms63776 KiB
#include <iostream> #include <vector> #include <map> #include <queue> #include <functional> #include <cassert> using namespace std; //#define debug #define int long long int N, M; int S, T; int U, V; #define assert_in(a)assert(a < N);assert(a >= 0); #define Qnode priority_queue<Node, vector<Node>, greater<Node>> vector<map<int, int>> G; class Node{ public: int cost, node, from; 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, Node node, vector<bool>& visited){ for(int next_node:G[node.node]){ if(!visited[next_node*2+1] && is_solut[next_node]){ visited[next_node*2+1] = true; Q->push({node.cost, next_node, node.node, true}); add_recurs(Q, G, node, visited); visited[next_node*2+1] = false; } } } const int INF = 1'000'000'000'000'000LL; vector<int> dp; vector<vector<int>> S_Tup; vector<vector<int>> S_Tdown; int dp_dfs(int node, bool used); int call_recurs(int node, vector<vector<int>> &_G){ int res = INF; for(int next_node:_G[node]){ if(is_solut[next_node]){ res = min(res, dp_dfs(node, true)); res = min(res, call_recurs(next_node, _G)); } } return res; } int deep = 0; int dp_dfs(int node, bool used){ //cout << node << " " << used << " "; int res = INF; int key = node*2+(used>0); //cout << key << ' ' << dp[key] << '\n'; if(dp[key] != -1){ /*#ifdef debug for(int i=0; i<deep; i++)cout << ' '; cout << node << ' ' << used << ':' << dp[key] << '\n'; #endif*/ return dp[key]; } dp[key] = INF; /*#ifdef debug for(int i=0; i<deep; i++)cout << ' '; cout << node << ' ' << used << ' ' << is_solut[node] << "->\n"; #endif*/ deep++; for(auto A:G[node]) res = min(res, dp_dfs(A.first, used)+A.second); if(is_solut[node]){ res = min( res, min( call_recurs(node, S_Tup), call_recurs(node, S_Tdown) ) ); } deep--; dp[key] = res; /*#ifdef debug for(int i=0; i<deep; i++)cout << ' '; cout << ":" << res << '\n'; #endif*/ return res; } signed main(){ cin >> N >> M; cin >> S >> T; cin >> U >> V; S--, U--, T--, V--; G = vector<map<int, int>>(N); assert_in(S);assert_in(T); assert_in(U);assert_in(V); for(int i=0; i<M; i++){ int node0, node1, cost; cin >> node0 >> node1 >> cost; node0--, node1--; assert_in(node0);assert_in(node1); G[node0][node1] = cost; G[node1][node0] = cost; } Qnode Q; vector<int> S_T(N, -1); S_Tup = vector<vector<int>>(N); S_Tdown = vector<vector<int>>(N); Q.push({0, S, -1}); while(!Q.empty()){ Node cur=Q.top(); Q.pop(); assert_in(cur.node); //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(cur.node == 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); /*#ifdef debug int temp=0; for(vector<int> A:S_Tup){ cout << temp << " :"; for(int n:A)cout << ' ' << n; cout << '\n'; temp++; } temp = 0; for(vector<int> A:S_Tdown){ cout << temp << " :"; for(int n:A)cout << ' ' << n; cout << '\n'; temp++; } for(int t:is_solut)cout << t << ' '; cout << '\n'; #endif*/ dp = vector<int>(N*2, -1); dp[V*2] = 0; dp[V*2+1] = 0; cout << dp_dfs(U, false) << '\n'; return 0;/*--------------------------------------------------------------------*/ Qnode Q2; Q2.push({0, U, -1, false}); vector<bool> U_V(N*2, false); while(!Q2.empty()){ Node cur=Q2.top(); Q2.pop(); assert_in(cur.node); //cout << cur.node << ' ' << cur.from << ' ' << cur.cost << '\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.node, cur.used}); } if(is_solut[cur.node] && !cur.used){ add_recurs(&Q2, S_Tup, cur, U_V); add_recurs(&Q2, S_Tdown, cur, 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...