#include using namespace std; int N, M, K; int a, b, c; long long dist[10005][21]; struct node { int idx; long long dist; struct node* next; }; node head[10005]; node pool[100005]; int nodecnt; node* getnode(int v,long long w) { pool[nodecnt] = { v,w,NULL }; return &pool[nodecnt++]; } struct point { int idx, ccnt; long long dist; bool operator >(const point& O) const { return dist > O.dist; } }; struct PQ { int qcnt; point arr[2500005]; void swap(point& a, point& b) { point temp = a; a = b; b = temp; } void push(point x) { arr[++qcnt] = x; int child = qcnt, parent = child / 2; while (parent >= 1 && arr[parent] > arr[child]) { swap(arr[parent], arr[child]); child = parent; parent /= 2; } } point pop() { point rslt = arr[1]; arr[1] = arr[qcnt--]; int parent = 1, child = 2; while (child <= qcnt) { if (child + 1 <= qcnt && arr[child] > arr[child + 1]) { child++; } if (arr[parent] > arr[child]) { swap(arr[parent], arr[child]); parent = child; child *= 2; } else break; } return rslt; } int empty() { return qcnt == 0; } }; PQ pq; void dijk(int sta) { dist[sta][0] = 0; pq.push({ sta,K,0 }); while (!pq.empty()) { point temp = pq.pop(); int ci = temp.idx; int cc = temp.ccnt; long long cd = temp.dist; if (cd > dist[ci][cc])continue; node* cur = head[ci].next; while (cur != NULL) { int ni = cur->idx; int nd = cur->dist; if (dist[ni][0] > cd + nd) { dist[ni][0] = cd + nd; pq.push({ ni,cc,dist[ni][0] }); } if (cc < K) { if (dist[ni][cc + 1] > cd) { dist[ni][cc + 1] = cd; pq.push({ ni,cc + 1,cd }); } } cur = cur->next; } } } int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N >> M >> K; for (int i = 1; i <= M; i++) { cin >> a >> b >> c; node* temp = getnode(b, c); temp->next = head[a].next; head[a].next = temp; temp = getnode(a, c); temp->next = head[b].next; head[b].next = temp; } for (int i = 1; i <= N; i++) { for (int j = 0; j <= K; j++) { dist[i][j] = 1e18; } } dijk(1); long long ans = 1e18; for (int i = 0; i <= K; i++) { ans = ans < dist[N][i] ? ans : dist[N][i]; } cout << ans << "\n"; return 0; }

제출 #143923

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: