結果
問題 | No.1382 Travel in Mitaru city |
ユーザー | 👑 ygussany |
提出日時 | 2021-02-07 20:57:57 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 53 ms / 2,000 ms |
コード長 | 1,593 bytes |
コンパイル時間 | 207 ms |
コンパイル使用メモリ | 30,464 KB |
実行使用メモリ | 7,168 KB |
最終ジャッジ日時 | 2024-07-04 14:04:42 |
合計ジャッジ時間 | 4,248 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 68 |
ソースコード
#include <stdio.h> typedef struct { int key, id; } data; typedef struct { data obj[100001]; int size; } max_heap; void push(data x, max_heap* h) { int i = ++(h->size), j = i >> 1; data tmp; h->obj[i] = x; while (j > 0) { if (h->obj[i].key > h->obj[j].key) { tmp = h->obj[j]; h->obj[j] = h->obj[i]; h->obj[i] = tmp; i = j; j >>= 1; } else break; } } data pop(max_heap* h) { int i = 1, j = 2; data output = h->obj[1], tmp; h->obj[1] = h->obj[(h->size)--]; while (j <= h->size) { if (j < h->size && h->obj[j^1].key > h->obj[j].key) j ^= 1; if (h->obj[j].key > h->obj[i].key) { tmp = h->obj[j]; h->obj[j] = h->obj[i]; h->obj[i] = tmp; i = j; j <<= 1; } else break; } return output; } typedef struct List { struct List *next; int v; } list; int main() { int i, N, M, S, T, u, w, P[100001]; list *adj[100001] = {}, e[200001], *p; scanf("%d %d %d %d", &N, &M, &S, &T); for (i = 1; i <= N; i++) scanf("%d", &(P[i])); for (i = 0; i < M; i++) { scanf("%d %d", &u, &w); e[i*2].v = w; e[i*2+1].v = u; e[i*2].next = adj[u]; e[i*2+1].next = adj[w]; adj[u] = &(e[i*2]); adj[w] = &(e[i*2+1]); } int X = P[S], Y = 0, flag[100001] = {}; max_heap h; data d; h.size = 0; d.key = P[S]; d.id = S; push(d, &h); flag[S] = 1; while (h.size > 0) { d = pop(&h); u = d.id; if (X > P[u]) { X = P[u]; Y++; } for (p = adj[u]; p != NULL; p = p->next) { w = p->v; if (flag[w] == 0) { flag[w] = 1; d.key = P[w]; d.id = w; push(d, &h); } } } printf("%d\n", Y); fflush(stdout); return 0; }