(1 ≤ n ≤ 1000, 0 ≤ m ≤ 250000, 1 ≤ k ≤ 100, mk ≤ 3000000, 1 ≤ a,b,c ≤ n, 1 ≤ c ≤ 1000)
Dijkstra
다익스트라 응용 문제인데 굉장히 흔한 유형이여서 거의 20분 컷을 했는데.. 이런 유형이 딱 그런 느낌이에요 알면 바로 풀리고, 모르면 좀 걸리는?
또 이제 구현 한번 해보면 이런 문제들은 금방 접근도 되고, 거의 바로 풀리는거라서 그렇게 어렵진 않았습니다.
그래도 꽤 난이도가 높게 나오는 문제여서 조금 설명을 하고 마치겠습니다.
현재 노드에서 k번 초과로 방문할 필요가 없음! 왜냐하면 여기랑 이어져있는 노드들은 k번 방문할 수 있는 경우.. 이미 이 노드를 지나가거나 다른 경우임.
그래서 이걸로 최적화를 해주고요. 그리고 k번째 방문했다면! result 업데이트 해주고… 이런 순서는 priority_queue로 처리해서 간단히 다익스트라 돌리면 되구요.
마지막으로 중요한 것은 방문 안 하면 -1을 출력하는데
이때 예외 처리를 조금 조심해줘야 합니다. 왜냐하면 k=1이면, 1번 도시 즉 시작 도시는 0이 찍힙니다. 이때 그냥 print를 N_i = 0이면 -1을 출력하게 했다..
그러면 이제 WA 뜨는겁니다. 뭐 이거는 문제를 읽고서 풀다보면 자연스럽게 해결할 수 있는 간단한 문제였구요.
재밌었습니다..
정답 코드 CPP</>
#include <iostream>#include <queue>#include <algorithm>#include<set>#include <map>using namespace std;using ll = long long;int inf = 1e9;int n, m, k;int graph[1001][1001];int visited[1001];ll result[1001];int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> k; for(int i = 0; i < m; i++){ int a, b, c; cin >> a >> b >> c; graph[a][b] = c; } for(int i = 1; i <= n; i++) visited[i] = 0; priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q; q.push({0, 1}); while(!q.empty()){ auto [cost, current] = q.top(); q.pop(); if(visited[current] >= k) continue; visited[current]++; if(visited[current] >= k) result[current] = cost; for(int i = 1; i <= n; i++){ if(graph[current][i] == 0 || visited[i] >= k) continue; q.push({graph[current][i] + cost, i}); } } if(k == 1) cout << result[1]; else { if(result[1] == 0) cout << -1; else cout << result[1]; } cout << "\n"; for(int i = 2; i <= n; i++){ if(result[i] == 0) cout << -1; else cout << result[i]; cout << "\n"; } return 0;}
compy.log