(BOJ) 4013 ATM

문제: https://www.acmicpc.net/problem/4013

 

 

문제 풀이:

https://hororolol.tistory.com/116랑 거의 비슷한 문제

다른점은

현재 위치에 레스토랑이 있다고 바로 break하는 것이 아니라 

최대값을 찾을 때까지 연산함

 

소스 코드:

int n, m, cost[500001], p[500001], scc[500001],dist[500001], res;
bool visit[500001], rest[500001];
vector<vector<int>> adj, adj2, scc_adj;
stack<int> st;
void dfs(int v) {
	visit[v] = true;
	for (int i : adj[v]) {
		if (visit[i]) continue;
		dfs(i);
	}
	st.push(v);
}
void rdfs(int v, int t) {
	visit[v] = true;
	scc[t] += cost[v];
	p[v] = t;
	for (int i : adj2[v]) {
		if (visit[i]) {
			if (p[i] != p[v]) {
				scc_adj[p[i]].push_back(p[v]);
			}
			continue;
		}
		else rdfs(i, t);
	}
}
void func(int cur, int cnt) {
	if (rest[cur]) {
		res = max(res, cnt);
	}
	for (int i : scc_adj[cur]) {
		func(i, cnt + scc[i]);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	cin >> n >> m;

	adj.resize(n + 1);
	adj2.resize(n + 1);
	for (int i = 0; i < m; i++) {
		int q, w;
		cin >> q >> w;
		adj[q].push_back(w);
		adj2[w].push_back(q);
	}
	for (int i = 1; i <= n; i++) {
		cin >> cost[i];
	}
	int start, k;
	cin >> start >> k;


	for (int i = 1; i <= n; i++) {
		if (visit[i]) continue;
		dfs(i);
	}
	memset(visit, false, sizeof(visit));

	int tmp = 0;
	while (!st.empty()) {
		int cur = st.top();
		st.pop();

		if (visit[cur]) continue;
		scc_adj.resize(++tmp);
		rdfs(cur, tmp - 1);
	}
	for (int i = 0; i < k; i++) {
		int q;
		cin >> q;
		rest[p[q]] = true;
	}
	queue<int> q;
	q.push(p[start]);
	dist[p[start]] = scc[p[start]];

	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		if (rest[cur]) {
			res = max(res, dist[cur]);
		}
		for (int i : scc_adj[cur]) {
			if (dist[i] < dist[cur] + scc[i]) {
				dist[i] = dist[cur] + scc[i];
				q.push(i);
			}
		}
	}
	cout << res << '\n';
	return 0;
}