結果
問題 | No.95 Alice and Graph |
ユーザー |
|
提出日時 | 2022-06-13 09:14:23 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 798 ms / 5,000 ms |
コード長 | 1,301 bytes |
コンパイル時間 | 1,851 ms |
コンパイル使用メモリ | 175,444 KB |
実行使用メモリ | 10,084 KB |
最終ジャッジ日時 | 2024-09-25 02:44:17 |
合計ジャッジ時間 | 5,041 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 14 |
ソースコード
#include<bits/stdc++.h> using namespace std; int main(){ int N, M, K, u, v; cin >> N >> M >> K; vector<vector<int>> dist(N, vector<int>(N, K + 10)); for(int i = 0; i < M; i++){ cin >> u >> v; u--, v--; dist[u][v] = dist[v][u] = 1; } for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ for(int k = 0; k < N; k++){ dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]); } } } vector<int> visit(1); long long ans = 0; for(int add = N - 1; add > 0 && visit.size() <= K; add--){ visit.push_back(add); vector<vector<int>> dp(1 << visit.size(), vector<int>(visit.size(), K + 10)); dp[1][0] = 0; for(int i = 0; i < (1 << visit.size()); i++){ for(int j = 0; j < visit.size(); j++){ if((~i >> j & 1) || dp[i][j] >= K)continue; for(int k = 0; k < visit.size(); k++){ if(i >> k & 1)continue; dp[i | (1 << k)][k] = min(dp[i | (1 << k)][k], dp[i][j] + dist[visit[j]][visit[k]]); } } } if(*min_element(dp.back().begin(), dp.back().end()) <= K)ans += (1ll << add) - 1; else visit.pop_back(); } cout << ans << '\n'; }