<링크>
https://www.acmicpc.net/problem/2611
<소스코드>
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 65 66 67 68 69 70 71 | #include<stdio.h> #include<queue> #include<vector> #include<stack> using namespace std; priority_queue<pair<int,int>> pq; //pair<cost,node> vector<pair<int, int>> adj[1001]; //pair<node,cost> void dijkstra(); int N, M; int dist[1001]; int before[1001]; int main() { scanf("%d%d", &N, &M); while (M--) { int a, b,c; scanf("%d%d%d", &a, &b, &c); adj[a].push_back({ b,c }); } dijkstra(); printf("%d\n", dist[1]); stack<int> st; int i = before[1]; while (i != 1) { st.push(i); i = before[i]; } printf("1 "); while (!st.empty()) { printf("%d ", st.top()); st.pop(); } printf("1"); } void dijkstra() { int m = -999999; for (int i = 1; i <= N; ++i) dist[i] = m; dist[1] = 0; pq.push({ 0,1 }); while (!pq.empty()) { int cur=pq.top().second; int cost = pq.top().first; pq.pop(); if (dist[cur] > cost) continue; int s = adj[cur].size(); for (int i = 0; i < s; ++i) { int toNode = adj[cur][i].first; int toCost = adj[cur][i].second; if (dist[toNode] < cost + toCost) { dist[toNode] = cost + toCost; before[toNode] = cur; if(toNode!=1) pq.push({ dist[toNode],toNode }); } } } return ; } | cs |
<풀이>
기존에 최단경로를 찾는 다익스트라 방식을 반대로 바꿔주면 된다.
그래서 priority_queue를 있는그대로 사용하면 된다.
최단경로때는 싸이클을 걱정 안해도 됐었지만
이거는 마지막에 1번노드를 지나쳐서 더 이동하면 무한대로 점수가 늘어나기 때문에
1번노드로 갈때는 값 갱신만 하고 큐에 넣지 않았다.
DP로도 풀수있는 문제이다.
<소스코드>
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<queue> #include<vector> #include<stack> #include<algorithm> using namespace std; void bfs(); vector<pair<int, int>> adj[1001]; //<node,cost> queue<int> q; int before[1001]; int dp[1001]; int degree[1001]; int main() { int N, M; scanf("%d%d", &N, &M); while (M--) { int a, b, c; scanf("%d%d%d", &a, &b, &c); adj[a].push_back({ b,c }); ++degree[b]; } bfs(); printf("%d\n", dp[1]); stack<int> st; int i = before[1]; while (i != 1) { st.push(i); i = before[i]; } printf("1 "); while (!st.empty()) { printf("%d ", st.top()); st.pop(); } printf("1"); } void bfs() { q.push(1); while (degree[1]) { int cur = q.front(); q.pop(); int s = adj[cur].size(); for (int i = 0; i < s; ++i) { int toNode = adj[cur][i].first; int toCost = adj[cur][i].second; --degree[toNode]; if (dp[toNode] < dp[cur] + toCost) { dp[toNode] = dp[cur] + toCost; before[toNode] = cur; } if (degree[toNode]==0) q.push(toNode); } } } | cs |
<풀이>
1번노드를 제외하고는 싸이클이 없으므로 이렇게 풀어도 될것같았다.
1. 차수를 미리 입력해놓는다.
2. 다음노드를 한번 확인할 때마다 다음노드의 차수를 하나 줄여준다.
3. 차수가 0이 되면 나한테 올 수 있는 노드들을 다 봤다는 뜻이다. 완벽하게 갱신됐다는 뜻이므로 다음 탐색을 위해 큐에 넣어준다.