#518295 (C++17) No.845 最長の切符

• 問題: No.845 最長の切符
• ユーザー: fura
• 提出日時: 2020-07-25 15:43:03
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 47 ms / 3,000 ms
• コード長: 574 bytes
• コンパイル時間: 1,912 ms
• コンパイル使用メモリ: 202,396 KB
• 実行使用メモリ: 7,864 KB
• 最終ジャッジ日時: 2024-06-27 06:58:48
• 合計ジャッジ時間: 3,271 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	4 ms; 7,680 KB
testcase_01	AC	4 ms; 7,680 KB
testcase_02	AC	4 ms; 7,644 KB
testcase_03	AC	4 ms; 7,808 KB
testcase_04	AC	4 ms; 7,704 KB
testcase_05	AC	4 ms; 7,680 KB
testcase_06	AC	4 ms; 7,712 KB
testcase_07	AC	4 ms; 7,692 KB
testcase_08	AC	4 ms; 7,784 KB
testcase_09	AC	4 ms; 7,820 KB
testcase_10	AC	4 ms; 7,708 KB
testcase_11	AC	4 ms; 7,656 KB
testcase_12	AC	4 ms; 7,660 KB
testcase_13	AC	4 ms; 7,680 KB
testcase_14	AC	4 ms; 7,728 KB
testcase_15	AC	11 ms; 7,720 KB
testcase_16	AC	33 ms; 7,864 KB
testcase_17	AC	9 ms; 7,632 KB
testcase_18	AC	18 ms; 7,728 KB
testcase_19	AC	7 ms; 7,720 KB
testcase_20	AC	39 ms; 7,736 KB
testcase_21	AC	47 ms; 7,680 KB
testcase_22	AC	10 ms; 7,680 KB
testcase_23	AC	5 ms; 7,736 KB
testcase_24	AC	33 ms; 7,808 KB
testcase_25	AC	3 ms; 7,728 KB
testcase_26	AC	32 ms; 7,680 KB
testcase_27	AC	3 ms; 7,680 KB
testcase_28	AC	40 ms; 7,680 KB
testcase_29	AC	3 ms; 7,680 KB

ソースコード

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

int main(){
	int n,m; scanf("%d%d",&n,&m);
	int d[16][16];
	memset(d,-1,sizeof d);
	rep(i,m){
		int u,v,c; scanf("%d%d%d",&u,&v,&c); u--; v--;
		d[u][v]=d[v][u]=max(d[u][v],c);
	}

	int dp[1<<16][16];
	memset(dp,-1,sizeof dp);
	rep(u,n) dp[1<<u][u]=0;
	rep(S,1<<n) rep(u,n) if(S>>u&1) {
		rep(v,n) if((S>>v&1)==0 && d[u][v]!=-1) {
			dp[S|1<<v][v]=max(dp[S|1<<v][v],dp[S][u]+d[u][v]);
		}
	}

	int ans=0;
	rep(S,1<<n) rep(u,n) ans=max(ans,dp[S][u]);
	printf("%d\n",ans);

	return 0;
}