結果
問題 | No.845 最長の切符 |
ユーザー |
![]() |
提出日時 | 2022-06-24 11:16:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 345 ms / 3,000 ms |
コード長 | 1,205 bytes |
コンパイル時間 | 1,062 ms |
コンパイル使用メモリ | 108,224 KB |
最終ジャッジ日時 | 2025-01-29 23:54:04 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include <cassert>#include <cmath>#include <algorithm>#include <iostream>#include <iomanip>#include <climits>#include <map>#include <queue>#include <set>#include <cstring>#include <vector>using namespace std;typedef long long ll;struct Edge {int to;int cost;Edge(int to = -1, int cost = -1) {this->to = to;this->cost = cost;}};int main() {int N, M;cin >> N >> M;vector<Edge> E[N + 1];for (int i = 0; i < M; ++i) {int a, b, c;cin >> a >> b >> c;--a;--b;E[a].push_back(Edge(b, c));E[b].push_back(Edge(a, c));}int L = pow(2, N);int dp[L][N];memset(dp, 0, sizeof(dp));int ans = 0;for (int c = 1; c < N; ++c) {for (int mask = 0; mask < L; ++mask) {if (__builtin_popcount(mask) != c) continue;for (int i = 0; i < N; ++i) {if ((mask >> i & 1) == 0) continue;for (Edge &e : E[i]) {if (mask >> e.to & 1) continue;int nmask = mask | (1 << e.to);int ncost = dp[mask][i] + e.cost;;dp[nmask][e.to] = max(dp[nmask][e.to], ncost);ans = max(ans, ncost);}}}}cout << ans << endl;return 0;}