結果
問題 | No.2387 Yokan Factory |
ユーザー |
![]() |
提出日時 | 2023-07-21 21:56:22 |
言語 | C (gcc 13.3.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,420 bytes |
コンパイル時間 | 267 ms |
コンパイル使用メモリ | 31,232 KB |
実行使用メモリ | 17,280 KB |
最終ジャッジ日時 | 2024-09-21 23:28:10 |
合計ジャッジ時間 | 7,841 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 TLE * 1 -- * 20 |
ソースコード
#include<stdio.h>long long int u[200005], v[200005];long long int h[1000006], l;long long int dist[100005];long long int comp_h(long long int a, long long int b, long long int z){if (z == 0){if (u[h[a]] > u[h[b]])return 1;elsereturn -1;}else{if (dist[h[a]] > dist[h[b]])return 1;elsereturn -1;}}void swap_h(long long int a, long long int b){long long int f = h[a];h[a] = h[b];h[b] = f;return;}void push(long long int ne, long long int z){h[l] = ne;long long int p = l;l++;for (; p > 0; p = (p - 1) / 2)if (comp_h((p - 1) / 2, p, z) > 0)swap_h((p - 1) / 2, p);return;}long long int pop(long long int z){l--;swap_h(0, l);long long int p = 0;for (;;){if (2 * p + 2 < l){if (comp_h(2 * p + 1, 2 * p + 2, z) > 0){if (comp_h(p, 2 * p + 2, z) > 0)swap_h(p, 2 * p + 2);p = 2 * p + 2;}else{if (comp_h(p, 2 * p + 1, z) > 0)swap_h(p, 2 * p + 1);p = 2 * p + 1;}}else if (2 * p + 1 < l){if (comp_h(p, 2 * p + 1, z) > 0)swap_h(p, 2 * p + 1);p = 2 * p + 1;}elsebreak;}return h[l];}long long int n, m, x;long long int a[200005], b[200005];long long int c[200005];long long int ind[200005];long long int d(long long int s){long long int i, j;for (i = 0; i < n; i++)dist[i] = 2e18;dist[0] = 0;l = 0;push(0, 1);while (l > 0){i = pop(1);j = ind[i];for (; u[c[j]] == i; j++){if (b[c[j]] < s)continue;if (dist[v[c[j]]] > dist[i] + a[c[j]]){dist[v[c[j]]] = dist[i] + a[c[j]];push(v[c[j]], 1);}}}return dist[n - 1];}int main(){scanf("%lld %lld %lld", &n, &m, &x);long long int i;for (i = 0; i < m; i++){scanf("%lld %lld %lld %lld", &u[i], &v[i], &a[i], &b[i]);u[i]--;v[i]--;u[i + m] = v[i];v[i + m] = u[i];a[i + m] = a[i];b[i + m] = b[i];}m *= 2;l = 0;for (i = 0; i < m; i++)push(i, 0);for (i = 0; i < m; i++)c[i] = pop(0);c[m] = m;u[m] = -1;long long int min, mid, max;for (i = 0; i < n; i++){min = -1;max = m;while (max - min > 1){mid = (max + min) / 2;if (u[c[mid]] < i)min = mid;elsemax = mid;}ind[i] = max;}min = -1;max = 1e9 + 7;while (max - min > 1){mid = (max + min) / 2;if (d(mid) > x)max = mid;elsemin = mid;}printf("%lld\n", min);return 0;}