解法
BitDP による全探索． \(N = 8, M = \frac{N(N-1)}{2}\) の最大ケースで 辺の選び方は\({}_{M}C_{N-1} \leq \frac{25^7}{7!} = 1,211,015\)通り であるから間に合う． 辺の取り方を \(s \in 2^{M}\) から選べばよい．
別のbitDPとして，頂点の選び方に対するbitDPがある． \(s \in 2^N\)に対して，新しい頂点を追加する． そのとき，辺が張られている物だけを追加する． ただし，暫定的なコストの最小が，最終的な最小になるとは限らない． よって，コストの集合をもっておく．
\(dp_{s} := s \in 2^N\) におけるコストの集合
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
// bitDP: edge
int main() {
ll n,m,k;
cin >> n >> m >> k;
rep(i,m){
ll a,b,c; cin >> a >> b >> c;
--a, --b;
ed[i] = {a,b,c};
}
ll ans = 8e15;
rep(s,1LL<<m){
if(pcntll(s) != n-1) continue;
UnionFind<ll> uf(n);
ll cost = 0;
rep(i,m) if(s>>i&1){
auto [a,b,c] = ed[i];
uf.merge(a,b);
cost += c;
}
if(uf.size(0) == n){
chmin(ans, cost%k);
}
}
cout << ans << endl;
return 0;
}
// bitDP: vertex
int main() {
ll n,m,k;
cin >> n >> m >> k;
vvll co(n, vll(n, INFL));
rep(i,m){
ll a,b,c; cin >> a >> b >> c;
--a, --b;
co[a][b] = c;
co[b][a] = c;
}
rep(i,n) dp[1LL<<i].insert(0);
rep(s,1LL<<n) rep(i,n) if(!(s>>i&1)){
rep(j,n) if(s>>j&1){
if(co[i][j]!=INFL){
for(auto x: dp[s]){
chmin(ans, x);
}
cout << ans << endl;
return 0;
}
*1:x + co[i][j])%k);
}
}
}
}
ll ans = INFL;
for(auto x:dp.back(
