代码

#ifndef DUCK_FASTIO_H
#define DUCK_FASTIO_H

typedef unsigned long duck_u64;
typedef long duck_i64;

typedef struct {
    duck_u64 abi_version;
    const char *stdin_ptr;
    duck_u64 stdin_size;
    char *stdout_ptr;
    duck_u64 stdout_limit;
    duck_u64 stdout_size;
    char *stderr_ptr;
    duck_u64 stderr_limit;
    duck_u64 stderr_size;
    const char *ib_ptr;
    duck_u64 ib_limit;
    char *ob_ptr;
    duck_u64 ob_limit;
    duck_u64 tsc_frequency;
} __attribute__((packed)) DuckInfo;

static __attribute__((always_inline)) inline DuckInfo *duck_info(long argc, char **argv) {
    char **p = argv + argc + 1;
    while (*p) ++p;
    duck_u64 *aux = (duck_u64 *)(p + 1);
    while (aux[0]) {
        if (aux[0] == 0x6b637564UL) return (DuckInfo *)aux[1];
        aux += 2;
    }
    return (DuckInfo *)0;
}

static __attribute__((always_inline)) inline duck_u64 duck_read_u64(const char **cursor) {
    const char *p = *cursor;
    while ((unsigned char)(*p - '0') > 9) ++p;
    duck_u64 value = 0;
    do {
        value = value * 10 + (unsigned char)(*p - '0');
        ++p;
    } while ((unsigned char)(*p - '0') <= 9);
    *cursor = p;
    return value;
}

static __attribute__((always_inline)) inline duck_i64 duck_read_i64(const char **cursor) {
    const char *p = *cursor;
    while (*p != '-' && (unsigned char)(*p - '0') > 9) ++p;
    int negative = *p == '-';
    p += negative;
    duck_u64 value = 0;
    do {
        value = value * 10 + (unsigned char)(*p - '0');
        ++p;
    } while ((unsigned char)(*p - '0') <= 9);
    *cursor = p;
    return negative ? -(duck_i64)value : (duck_i64)value;
}

static __attribute__((always_inline)) inline char *duck_write_u64(char *out, duck_u64 value) {
    char tmp[24];
    unsigned n = 0;
    do {
        tmp[n++] = (char)('0' + value % 10);
        value /= 10;
    } while (value);
    do *out++ = tmp[--n]; while (n);
    return out;
}

static __attribute__((always_inline)) inline char *duck_write_i64(char *out, duck_i64 value) {
    if (value < 0) {
        *out++ = '-';
        return duck_write_u64(out, (duck_u64)(-value));
    }
    return duck_write_u64(out, (duck_u64)value);
}

static __attribute__((always_inline, noreturn)) inline void duck_exit(void) {
    __asm__ volatile("mov $60,%%eax;xor %%edi,%%edi;syscall" ::: "rax", "rdi", "rcx", "r11", "memory");
    __builtin_unreachable();
}

#endif


typedef unsigned int u32;
typedef unsigned long u64;

enum { MAXN = 100000, MAXM = 200000, MAXK = 50 };
static const u64 INF = (u64)-1 / 4;

static int head_forward[MAXN], head_reverse[MAXN];
static int next_forward[MAXM], next_reverse[MAXM];
static u32 edge_from[MAXM], edge_to[MAXM], edge_weight[MAXM];
static unsigned char edge_extra[MAXM];

static u64 distance_to_exit[MAXN], distance_from_start[MAXN];
static u64 heap_distance[MAXM + 8];
static u32 heap_vertex[MAXM + 8];
static u32 heap_size;

static unsigned char active[MAXN];
static u32 indegree[MAXN], order[MAXN], queue_vertex[MAXN];
static u32 ways[(MAXK + 1) * MAXN];

static __attribute__((always_inline)) inline void heap_push(u32 vertex, u64 distance) {
    u32 at = ++heap_size;
    while (at > 1) {
        u32 parent = at >> 1;
        if (heap_distance[parent] <= distance) break;
        heap_distance[at] = heap_distance[parent];
        heap_vertex[at] = heap_vertex[parent];
        at = parent;
    }
    heap_distance[at] = distance;
    heap_vertex[at] = vertex;
}

static __attribute__((always_inline)) inline u32 heap_pop(u64 *distance) {
    u32 result = heap_vertex[1];
    *distance = heap_distance[1];
    u32 vertex = heap_vertex[heap_size];
    u64 value = heap_distance[heap_size--];
    if (heap_size) {
        u32 at = 1;
        while ((at << 1) <= heap_size) {
            u32 child = at << 1;
            if (child < heap_size && heap_distance[child + 1] < heap_distance[child])
                ++child;
            if (heap_distance[child] >= value) break;
            heap_distance[at] = heap_distance[child];
            heap_vertex[at] = heap_vertex[child];
            at = child;
        }
        heap_distance[at] = value;
        heap_vertex[at] = vertex;
    }
    return result;
}

static void dijkstra(u32 n, u32 source, int *head, int *next, int reverse,
                     u64 *distance) {
    for (u32 i = 0; i < n; ++i) distance[i] = INF;
    heap_size = 0;
    distance[source] = 0;
    heap_push(source, 0);
    while (heap_size) {
        u64 current_distance;
        u32 u = heap_pop(&current_distance);
        if (current_distance != distance[u]) continue;
        for (int e = head[u]; e >= 0; e = next[e]) {
            u32 v = reverse ? edge_from[e] : edge_to[e];
            u64 candidate = current_distance + edge_weight[e];
            if (candidate < distance[v]) {
                distance[v] = candidate;
                heap_push(v, candidate);
            }
        }
    }
}

__attribute__((noreturn))
void __libc_start_main(void *unused, long argc, char **argv) {
    (void)unused;
    DuckInfo *info = duck_info(argc, argv);
    const char *input = info->stdin_ptr;
    char *out = info->stdout_ptr;
    u32 tests = (u32)duck_read_u64(&input);

    while (tests--) {
        u32 n = (u32)duck_read_u64(&input);
        u32 m = (u32)duck_read_u64(&input);
        u32 limit = (u32)duck_read_u64(&input);
        u32 modulus = (u32)duck_read_u64(&input);
        for (u32 i = 0; i < n; ++i) head_forward[i] = head_reverse[i] = -1;
        for (u32 e = 0; e < m; ++e) {
            u32 u = (u32)duck_read_u64(&input) - 1;
            u32 v = (u32)duck_read_u64(&input) - 1;
            u32 w = (u32)duck_read_u64(&input);
            edge_from[e] = u;
            edge_to[e] = v;
            edge_weight[e] = w;
            next_forward[e] = head_forward[u];
            head_forward[u] = (int)e;
            next_reverse[e] = head_reverse[v];
            head_reverse[v] = (int)e;
        }

        dijkstra(n, n - 1, head_reverse, next_reverse, 1, distance_to_exit);
        if (distance_to_exit[0] == INF) {
            *out++ = '0';
            *out++ = '\n';
            continue;
        }
        dijkstra(n, 0, head_forward, next_forward, 0, distance_from_start);

        u64 maximum_length = distance_to_exit[0] + limit;
        u32 active_count = 0;
        for (u32 u = 0; u < n; ++u) {
            int valid = distance_from_start[u] != INF && distance_to_exit[u] != INF &&
                        distance_from_start[u] + distance_to_exit[u] <= maximum_length;
            active[u] = (unsigned char)valid;
            indegree[u] = 0;
            active_count += (u32)valid;
        }

        for (u32 e = 0; e < m; ++e) {
            u32 u = edge_from[e], v = edge_to[e];
            if (distance_to_exit[u] == INF || distance_to_exit[v] == INF) {
                edge_extra[e] = 255;
                continue;
            }
            u64 extra = (u64)edge_weight[e] + distance_to_exit[v] - distance_to_exit[u];
            edge_extra[e] = extra <= limit ? (unsigned char)extra : 255;
            if (extra == 0 && active[u] && active[v]) ++indegree[v];
        }

        u32 queue_head = 0, queue_tail = 0;
        for (u32 u = 0; u < n; ++u)
            if (active[u] && indegree[u] == 0) queue_vertex[queue_tail++] = u;
        u32 ordered = 0;
        while (queue_head < queue_tail) {
            u32 u = queue_vertex[queue_head++];
            order[ordered++] = u;
            for (int e = head_forward[u]; e >= 0; e = next_forward[e]) {
                u32 v = edge_to[e];
                if (edge_extra[e] == 0 && active[v] && --indegree[v] == 0)
                    queue_vertex[queue_tail++] = v;
            }
        }
        if (ordered != active_count) {
            *out++ = '-';
            *out++ = '1';
            *out++ = '\n';
            continue;
        }

        u32 states = (limit + 1) * n;
        __builtin_memset(ways, 0, (u64)states * sizeof(*ways));
        ways[0] = modulus == 1 ? 0 : 1;
        for (u32 extra_used = 0; extra_used <= limit; ++extra_used) {
            u32 *current = ways + (u64)extra_used * n;
            for (u32 index = 0; index < ordered; ++index) {
                u32 u = order[index];
                u32 value = current[u];
                if (!value) continue;
                for (int e = head_forward[u]; e >= 0; e = next_forward[e]) {
                    unsigned delta = edge_extra[e];
                    if (delta > limit - extra_used) continue;
                    u32 v = edge_to[e];
                    u32 *target = ways + (u64)(extra_used + delta) * n + v;
                    u32 sum = *target + value;
                    if (sum >= modulus) sum -= modulus;
                    *target = sum;
                }
            }
        }

        u32 answer = 0;
        for (u32 extra_used = 0; extra_used <= limit; ++extra_used) {
            answer += ways[(u64)extra_used * n + n - 1];
            if (answer >= modulus) answer -= modulus;
        }
        out = duck_write_u64(out, answer);
        *out++ = '\n';
    }

    info->stdout_size = (u64)(out - info->stdout_ptr);
    duck_exit();
}

int main(void) {}

评测结果