Submission #66774028

Source Code Expand

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

typedef pair<int, int> pii;
const int MAXN = 1e3 + 5;
vector<pii> G[MAXN];
priority_queue<pii> Q;
int a[MAXN][1 << 10];

void add(int u, int v, int w) {
    G[u].push_back({v, w});
}

int main() {
    int n, m, u, v, w, ns, ans = 1e9 + 5;
    cin >> n >> m;
    for (int i = 1; i <= m; i ++) {
        cin >> u >> v >> w;
        add(u, v, w);
    }
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j < (1 << 10); j ++) {
            a[i][j] = 1e9 + 5;
        }
    }
    a[1][0] = 0;
    Q.push({0, 1});
    while (!Q.empty()) {
        auto [s, u] = Q.top();
        Q.pop();
        if (u == n) {
            ans = min(ans, s);
            continue;
        }
        if (s > a[u][s]) {
            continue;
        }
        for (auto [v, w] : G[u]) {
            ns = s ^ w;
            if (a[v][ns] > ns) {
                a[v][ns] = ns;
                Q.push({ns, v});
            }
        }
    }
    cout << (ans == 1e9 + 5 ? -1 : ans);
    return 0;
}

Submission Info

Submission Time
Task D - XOR Shortest Walk
User FlowerAccepted
Language C++ 17 (gcc 12.2)
Score 0
Code Size 1165 Byte
Status WA
Exec Time 37 ms
Memory 7584 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 2
WA × 1
AC × 24
WA × 9
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt, hand_08.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
hand_01.txt AC 1 ms 3548 KiB
hand_02.txt WA 1 ms 3560 KiB
hand_03.txt AC 1 ms 3560 KiB
hand_04.txt AC 1 ms 3644 KiB
hand_05.txt AC 1 ms 3508 KiB
hand_06.txt AC 1 ms 3500 KiB
hand_07.txt AC 1 ms 3564 KiB
hand_08.txt AC 1 ms 3508 KiB
random_01.txt AC 1 ms 3712 KiB
random_02.txt AC 3 ms 5872 KiB
random_03.txt AC 1 ms 3500 KiB
random_04.txt AC 2 ms 5108 KiB
random_05.txt AC 1 ms 3600 KiB
random_06.txt AC 2 ms 4396 KiB
random_07.txt AC 1 ms 3620 KiB
random_08.txt AC 3 ms 5736 KiB
random_09.txt AC 1 ms 3556 KiB
random_10.txt WA 3 ms 6900 KiB
random_11.txt AC 1 ms 3568 KiB
random_12.txt AC 3 ms 5908 KiB
random_13.txt WA 8 ms 3804 KiB
random_14.txt WA 29 ms 4740 KiB
random_15.txt WA 3 ms 3724 KiB
random_16.txt AC 2 ms 5976 KiB
random_17.txt WA 4 ms 7572 KiB
random_18.txt AC 4 ms 7536 KiB
random_19.txt AC 17 ms 7584 KiB
random_20.txt AC 37 ms 7500 KiB
random_21.txt WA 3 ms 7508 KiB
random_22.txt WA 4 ms 7568 KiB
sample_01.txt AC 1 ms 3464 KiB
sample_02.txt WA 1 ms 3548 KiB
sample_03.txt AC 3 ms 7544 KiB