<링크>
https://www.acmicpc.net/problem/1005
<풀이_1>
아무생각없이 하면 틀리는 이유는, 내가 완벽하지 못한데 다른 노드들을 갱신할 때 쓰이기 때문이다.
...-> A -> C ->...
...-> B -> C ->...
이렇게 둘이 있을 때
아직 A가 완벽하게 갱신이 안돼서 최댓값을 못알아냈는데 C에게 정보를 제공해버렸다고 치자.
근데 나중에 A로 가는 다른 경로를 찾아서 A가 갱신이되면 C도 바꿔줘야되고 그 뒤로 연관된 모든놈들을 다 바꿔야된다.
그래서 나중에 피똥쌀 수가 있다. 그럼 A를 믿을수있게끔 만들어주는 방법은 A로 가는 모든경로들을 다 보면된다.
노드의 차수를 이용한다.
내 이전에 오는 노드들을 다 봤을때, 그 때 비로소 내가 다른 노드들을 갱신하는데 사용될 수 있게끔 했다.
<소스코드>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | #include<stdio.h> #include<vector> #include<queue> #include<algorithm> #include<string.h> using namespace std; vector<int> adj[1001]; queue<int> q; int time[1001]; int degree[1001]; int dp[1001]; int W; void bfs(); int main() { int T; scanf("%d", &T); while (T--) { memset(dp, 0, sizeof(dp)); memset(degree, 0, sizeof(degree)); q = queue<int>(); for (int i = 1; i <= 1000; ++i) adj[i] = vector<int>(); int N, M; scanf("%d%d", &N, &M); for(int i=1;i<=N;++i) scanf("%d", time + i); while (M--) { int a, b; scanf("%d%d", &a, &b); adj[a].push_back(b); ++degree[b]; } scanf("%d", &W); for (int i = 1; i <= N; ++i) if (degree[i] == 0) { q.push(i); dp[i] = time[i]; } bfs(); printf("%d\n", dp[W]); } } void bfs() { while (degree[W] != 0) { int cur = q.front(); q.pop(); int s = adj[cur].size(); for (int i = 0; i < s; ++i) { int to=adj[cur][i]; dp[to] = max(dp[cur] + time[to], dp[to]); --degree[to]; if (degree[to] == 0) q.push(to); } } } | cs |
<풀이_2>
목적지 W를 시작점으로 거꾸로 dfs하면 된다.
입력 받을때도 인접리스트를 싹다 거꾸로 받아주면 역방향 그래프가 완성된다.
연결리스트가 없는 끝노드까지 가면 걔는 시작건물이니깐 그냥 자기건물시간만 리턴해준다.
불필요한 재귀를 줄이기 위해 memozation을 사용했다.
<소스코드>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | #include<stdio.h> #include<vector> #include<algorithm> #include<string.h> using namespace std; int dp[1001]; int t[1001]; vector<int> adj[1001]; int solve(int); int main() { int T; scanf("%d", &T); while (T--) { memset(dp, -1, sizeof(dp)); for (int i = 1; i <= 1000; ++i) adj[i].clear(); int N, M; scanf("%d%d", &N, &M); for (int i = 1; i <= N; ++i) scanf("%d", t + i); while (M--) { int a, b; scanf("%d%d", &a, &b); adj[b].push_back(a); } int W; scanf("%d", &W); printf("%d\n",solve(W)); } } int solve(int i) { int &ret = dp[i]; if (ret != -1) return ret; int m = 0; for (int to : adj[i]) m = max(m, solve(to)); return ret = m + t[i]; } | cs |
