提出 #47485327

---

ソースコード 拡げる

#include <bits/stdc++.h>
#include <atcoder/modint>

namespace {
using ModInt [[maybe_unused]] = atcoder::modint998244353;
using Num [[maybe_unused]] = long long int;
using Vec [[maybe_unused]] = std::vector<Num>;
using Set [[maybe_unused]] = std::set<Num>;
using Mset [[maybe_unused]] = std::multiset<Num>;
// using Edges [[maybe_unused]] = std::vector<std::vector<Num>>;

template<typename T>
using Q [[maybe_unused]] = std::queue<T>;

template<typename T>
using PQ [[maybe_unused]] = std::priority_queue<T, std::vector<T>, std::greater<T>>;
}

struct Edge {
    Num to {0};
    Num cost {0};
};

using Edges = std::vector<std::vector<Edge>>;
Edges edges;
Num n;
Num m;
Num k;
Num answer;

void visit_dfs(Vec& vs, Num cost) {
    if (vs.size() == static_cast<size_t>(n)) {
        answer = std::min(answer, cost % k);
        return;
    }

    const auto froms = vs;
    for(const auto& from : froms) {
        for(const auto& [next, c] : edges[from]) {
            auto it = std::find(vs.begin(), vs.end(), next);
            if (it != vs.end()) {
                continue;
            }

            vs.push_back(next);
            visit_dfs(vs, cost + c);
            vs.pop_back();
        }
    }
}

void solve(std::istream& is, std::ostream& os) {
    is >> n >> m >> k;
    edges.resize(n);
    answer = k;

    for(Num i{0}; i<m; ++i) {
        Num u, v, w;
        is >> u >> v >> w;
        --u;
        --v;
        edges.at(u).push_back(Edge{v, w});
        edges.at(v).push_back(Edge{u, w});
    }

    Vec vs {0};
    visit_dfs(vs, 0);
    os << answer << "\n";
}

int main(void) {
    solve(std::cin, std::cout);
    return 0;
}

提出情報

ジャッジ結果