#include #include using namespace std; int N, M, K; int a, b, c; long long dist[10005][2]; 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[1000005]; 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; 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 > 0) { if (dist[ni][1] > cd) { dist[ni][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++) { dist[i][0] = dist[i][1] = 1e18; } dijk(1); //for (int i = 1; i <= N; i++) { // cout << dist[i][0] << " " << dist[i][1] << "\n"; //} cout << min(dist[N][0], dist[N][1]) << "\n"; return 0; }

제출 #143911

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: