#include #include #include #include using namespace std; typedef long long ll; struct Node { int idx; // idx = 포장 횟수 vector sum; // first -> 인접리스트 idx, second -> 거리 vector> adj; }; int N, M, K; vector NodeList; ll answer; void Dijk(int startIdx, int endIdx) { queue> q; q.push({ NodeList[startIdx],0 }); NodeList[1].sum[0] = 0; while (!q.empty()) { // first = Node, second = 포장한 횟수 pair cur = q.front(); q.pop(); if (cur.second > K)continue; if (cur.first.idx == N)continue; for (auto& p : cur.first.adj) { if (p.first == 1)continue; if (NodeList[p.first].sum[cur.second] == -1) { NodeList[p.first].sum[cur.second] = NodeList[cur.first.idx].sum[cur.second] + p.second; q.push({ NodeList[p.first],cur.second }); if (NodeList[p.first].sum[cur.second + 1] == -1) { NodeList[p.first].sum[cur.second + 1] = NodeList[cur.first.idx].sum[cur.second]; q.push({ NodeList[p.first],cur.second + 1 }); } else { if (NodeList[p.first].sum[cur.second + 1] > NodeList[cur.first.idx].sum[cur.second] + p.second) { q.push({ NodeList[p.first],cur.second + 1 }); NodeList[p.first].sum[cur.second + 1] = NodeList[cur.first.idx].sum[cur.second] + p.second; } } } else { if (NodeList[p.first].sum[cur.second] > NodeList[cur.first.idx].sum[cur.second] + p.second) { NodeList[p.first].sum[cur.second] = NodeList[cur.first.idx].sum[cur.second] + p.second; q.push({ NodeList[p.first],cur.second }); } if (NodeList[p.first].sum[cur.second + 1] == -1) { NodeList[p.first].sum[cur.second + 1] = NodeList[cur.first.idx].sum[cur.second]; q.push({ NodeList[p.first],cur.second + 1 }); } else { if (NodeList[p.first].sum[cur.second + 1] > NodeList[cur.first.idx].sum[cur.second]) { NodeList[p.first].sum[cur.second + 1] = NodeList[cur.first.idx].sum[cur.second]; q.push({ NodeList[p.first],cur.second + 1 }); } } } } } return; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> N >> M >> K; NodeList.resize(N + 1); answer = 0; for (int i = 0; i < M; i++) { int a, b; ll c; cin >> a >> b >> c; NodeList[a].idx = a; NodeList[b].idx = b; NodeList[a].sum.resize(K + 2, -1); NodeList[b].sum.resize(K + 2, -1); NodeList[a].adj.push_back({ b,c }); NodeList[b].adj.push_back({ a,c }); } Dijk(1, N); ll minValue = 1e9; NodeList[N].sum.erase(remove(NodeList[N].sum.begin(), NodeList[N].sum.end(), -1), NodeList[N].sum.end()); sort(NodeList[N].sum.begin()+1, NodeList[N].sum.end()); cout << NodeList[N].sum[0] << '\n'; return 0; }

제출 #152279

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: