Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Make CSP great again
- #include <bits/stdc++.h>
- #define TASK "TESTCODE"
- using namespace std;
- const int N = 5e5;
- int Low[N + 1], Num[N + 1], n, Component[N + 1], w[N + 1], Money[N + 1], m, s, p, Count = 0, componentcount = 0, res = 0, d[N + 1];
- vector<int> Adj[N + 1];
- bool Free[N + 1], Junction[N + 1];
- stack<int> Stack;
- void read()
- {
- cin >> n >> m;
- fill(Free + 1, Free + n + 1, true);
- fill(Junction + 1, Junction + n + 1, false);
- for(int i = 1; i <= m; ++ i)
- {
- int u, v;
- cin >> u >> v;
- Adj[u].push_back(v);
- }
- for (int i = 1; i <= n; ++ i)
- {
- cin >> w[i];
- }
- cin >> s >> p;
- for (int i = 1; i <= p; ++ i)
- {
- int u;
- cin >> u;
- Junction[u] = true;
- }
- }
- void Visit(int u)
- {
- ++Count;
- Low[u] = Num[u] = Count;
- Stack.push(u);
- for (int v : Adj[u])
- {
- if (Free[v])
- {
- if (Num[v] != 0)
- {
- Low[u] = min(Low[u], Num[v]);
- }
- else
- {
- Visit(v);
- Low[u] = min(Low[u], Low[v]);
- }
- }
- }
- if (Num[u] == Low[u])
- {
- vector<int> P;
- ++componentcount;
- int sum = 0;
- int v;
- do
- {
- v = Stack.top();
- Stack.pop();
- P.push_back(v);
- sum += w[v];
- Component[v] = componentcount;
- Free[v] = false;
- }
- while (v != u);
- for (int v : P)
- {
- Money[v] = sum;
- }
- }
- }
- void DFS(int u)
- {
- if (Junction[u])
- {
- res = max(res, d[u]);
- }
- for (int v : Adj[u])
- {
- int add = 0;
- if (Component[u] != Component[v])
- {
- add = Money[v];
- }
- if (d[u] + add > d[v])
- {
- d[v] = d[u] + add;
- DFS(v);
- }
- }
- }
- void Debug()
- {
- for (int i = 1; i <= n; ++ i)
- {
- cout << Component[i] << ' ';
- }
- }
- void solve()
- {
- for (int i = 1; i <= n; ++ i)
- {
- if (Num[i] == 0)
- {
- Visit(i);
- }
- }
- d[s] = Money[s];
- DFS(s);
- cout << res;
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- //freopen(TASK".INP", "r", stdin);
- //freopen(TASK".OUT", "w", stdout);
- int t = 1;
- bool typetest = false;
- if (typetest)
- {
- cin >> t;
- }
- for (int __ = 1; __ <= t; ++ __)
- {
- read();
- solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement