Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Snippets: https://github.com/prabhavdogra/CPSnippets;
- #include <bits/stdc++.h>
- using namespace std;
- #define int long long int
- signed main() {
- cin.tie(nullptr)->sync_with_stdio(false);
- int n, m, s, e, u, v;
- cin >> n >> m >> s >> e;
- s--; e--;
- vector<int> fun(n);
- vector<vector<int>> adj(n);
- for(auto &it: fun)
- cin >> it;
- for(int i = 0; i < m; i++) {
- cin >> u >> v;
- adj[u - 1].push_back(v - 1);
- }
- auto topo_dfs = [&] (vector<vector<int>> &adj_) -> vector<int> {
- vector<int> vis(adj_.size());
- vector<int> order_;
- auto helper = [&] (const auto &self, int node) -> void {
- vis[node] = 1;
- for(auto &child: adj_[node])
- if(!vis[child])
- self(self, child);
- order_.push_back(node);
- };
- for(int i = 0; i < n; i++)
- if(!vis[i])
- helper(helper, i);
- reverse(order_.begin(), order_.end());
- return order_;
- };
- auto order = topo_dfs(adj);
- auto scc = [&] (vector<vector<int>> adj_, vector<int> order_) -> vector<vector<int>> {
- vector<vector<int>> radj_(adj_.size());
- for(int i = 0; i < (int)adj_.size(); i++)
- for(auto j: adj[i])
- radj_[j].push_back(i);
- vector<vector<int>> components_;
- auto vis = vector<int>(n, 0);
- auto helper = [&] (const auto &self, int node) -> void {
- vis[node] = 1;
- components_.back().push_back(node);
- for(auto child: radj_[node])
- if(!vis[child])
- self(self, child);
- };
- for(auto node: order) {
- if(!vis[node]) {
- components_.push_back(vector<int>());
- helper(helper, node);
- }
- }
- return components_;
- };
- auto components = scc(adj, order);
- vector<int> num(n);
- vector<int> color_(n);
- auto condense = [&] (vector<vector<int>> adj_, vector<vector<int>> &components_) -> pair<vector<int>, vector<vector<int>>> {
- vector<vector<int>> adj_scc_(adj_.size());
- for(auto &component_: components_) {
- int col_ = component_[0];
- int res = 0;
- for(auto it: component_) {
- color_[it] = col_;
- res += fun[it];
- }
- fun[col_] = res;
- }
- for(int i = 0; i < n; i++) {
- for(auto j: adj_[i]) {
- if(color_[i] != color_[j])
- adj_scc_[color_[i]].push_back(color_[j]);
- }
- }
- vector<int> order_scc_;
- for(auto component_: components_)
- order_scc_.push_back(component_[0]);
- return {order_scc_, adj_scc_};
- };
- auto [order_scc, adj_scc] = condense(adj, components);
- while(order_scc.size()) {
- if(color_[e] != order_scc.back())
- order_scc.pop_back();
- else break;
- }
- vector<int> dp(n);
- while(order_scc.size()) {
- int x = order_scc.back();
- order_scc.pop_back();
- int val = 0;
- for(auto neighour: adj_scc[x])
- val = max(val, dp[neighour]);
- dp[x] = val + fun[x];
- }
- cout << dp[color_[s]] << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement