#include<stdio.h> #include<algorithm> #include<vector> using namespace std; const int MAX_N = 500000; int n, m, atm[MAX_N + 1], w[MAX_N + 1], s, p; bool ck[MAX_N + 1], r[MAX_N + 1]; vector<int> adj[2][MAX_N + 1], vis; void dfs(int x, bool t) { if (ck[x] != t) return; ck[x] = !t; for (auto it : adj[t][x]) dfs(it, t); vis.push_back(x); } int main() { scanf("%d %d", &n, &m); for (int i = 0; i < m; i++) { int x, y; scanf("%d %d", &x, &y); adj[0][x].push_back(y); adj[1][y].push_back(x); } for (int i = 1; i <= n; i++) scanf("%d", &atm[i]); scanf("%d %d", &s, &p); for (int i = 0; i < p; i++) { int x; scanf("%d", &x); r[x] = true; } for (int i = 1; i <= n; i++) dfs(i, false); vector<int> tvis = vis; int res = 0, flag = 0; for (int i = tvis.size() - 1; i >= 0; i--) { if (!ck[tvis[i]]) continue; vis.clear(); dfs(tvis[i], true); int sum = 0, ex = 0, maxi = 0; for (auto it : vis) { flag |= it == s; ex |= r[it]; sum += atm[it]; maxi = max(maxi, w[it]); } if (flag) { for (auto it : vis) for (auto t : adj[0][it]) if (ck[t]) w[t] = sum + maxi; if (ex) res = max(res, sum + maxi); } } printf("%d", res); return 0; }
4013번: ATM
https://www.acmicpc.net/problem/4013
피드 구독하기:
댓글
(
Atom
)
댓글 없음 :
댓글 쓰기