提出 #47494911

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ld = long double;
using pll = pair<ll, ll>;
// and so on
ll mp[8][8];
int idx[8];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll N, M, K;
    cin >> N >> M >> K;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) mp[i][j] = -1;
        idx[i] = i;
    }
    for (int i = 0; i < M; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        mp[a - 1][b - 1] = mp[b - 1][a - 1] = c;
    }
    ll ans = 1LL << 60;
    do {
        queue<ll> q[2];
        q[0].push(0);
        bool isok = true;
        for (int i = 1; i < N; i++) {
            queue<ll> &nxt = q[i % 2];
            queue<ll> &cnt = q[1 - i % 2];
            int e = idx[i];
            ll lst[8] = {
                0,
            };
            for (int j = 0; j < i; j++) {
                lst[j] = mp[idx[j]][e];
            }
            if (cnt.empty()) {
                isok = false;
                break;
            }
            while (!cnt.empty()) {
                ll x = cnt.front();
                cnt.pop();
                for (int j = 0; j < i; j++) {
                    if (lst[j] >= 0) nxt.push((x + lst[j]) % K);
                }
            }
        }
        queue<ll> fin = q[1 - N % 2];
        isok &= !fin.empty();
        if (isok) {
            while (!fin.empty()) {
                ll x = fin.front();
                fin.pop();
                ans = min(ans, x);
            }
        }
    } while (next_permutation(idx + 1, idx + N));
    cout << ans;
}

提出情報

ジャッジ結果