作成日
最終更新
記事区分目次
クラウドネイティブなアーキテクチャを設計するのが好きです。主にGCPを利用しています。
工作HardwareHubからのお知らせ
頂点数nが小さい場合に限れば、巡回セールスマン問題はビットDPの手法でうまく解くことができます。
サンプルインプット
頂点数n (<=15)、辺の数mの重みつき有向グラフがあり、最初頂点0にいるとします。すべての頂点を訪れて頂点0に戻ってきたときの重みの総和の最小値を求めましょう。
n(頂点数) m(辺の数)
Vi1 Vj1 cost1
Vi2 Vj2 cost2
...
Vim Vjm costm
bitDP.in
5 8
0 1 3
0 3 4
1 2 5
2 0 4
2 3 5
3 4 3
4 0 7
4 1 6
サンプルコード
bitDP.cpp
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
#define REP(i,n) for(int i=0; i<(int)n; i++)
#define INF 1e9
const int MAXN=16;
int n;
int d[MAXN][MAXN];
int dp[1<<MAXN][MAXN];
int rec(int S, int v) {
if(dp[S][v] >= 0) return dp[S][v];
if(S==(1<<n)-1 && v==0) return dp[S][v]=0;
int tmp=INF;
REP(u,n) if(!(S>>u & 1)) tmp=min(tmp, rec(S|1<<u,u)+d[v][u]);
return dp[S][v]=tmp;
}
int main() {
int m;
cin>>n>>m;
REP(i,n) REP(j,n) d[i][j]=d[j][i]=INF;
REP(i,m) {int a,b,c; cin>>a>>b>>c; d[a][b]=c;}
fill((int *)dp, (int *)(dp+(1<<MAXN)), -1);
cout << rec(0,0) << endl;
return 0;
}
実行例
$ g++ -Wall bitDP.cpp && ./a.out < bitDP.in
22
0
記事の執筆者にステッカーを贈る
有益な情報に対するお礼として、またはコメント欄における質問への返答に対するお礼として、 記事の読者は、執筆者に有料のステッカーを贈ることができます。
さらに詳しく →
Feedbacks
ログインするとコメントを投稿できます。
関連記事
- ダウンキャスト (C++をもう一度)実行時型情報 RTTI #include <iostream> #include <typeinfo> using namespace std; class MyClass { public: virtual ~MyClass() {} // typeid で正しい RTTI // (RunTime Type Information; 実行時型情報) ...
- 競技プログラミングの基本処理チートシート (C++)限られた時間の中で問題を解くために必要となる、競技プログラミングにおける基本的な処理のチートシートです。競プロにおけるメジャー言語 C++ を利用します。その際 C++11 の機能は利用せず C++03 の機能の範囲内で記述します。 頻度高く定期的に開催されるコンテスト AtCoder Codeforces main.cpp #include <iostream>
- 構造体と列挙体 (C++をもう一度)構造体 #include <iostream> using namespace std; struct MyStruct { char charval; int intval; }; void Show(MyStruct* obj) { cout << obj->intval << endl; } int main() { ...
- Valgrind による C/C++ メモリリーク検出JVM メモリリークでは JDK の jstat や jmap で原因を調査できます。C/C++ では valgrind の Memcheck ツールが利用できます。valgrind には複数のツールが含まれており既定のツールが Memcheck です。他のツールを利用する場合は --tool オプションで指定します。 [簡単な利用例](h
- クラスの基本/初期化 (C++をもう一度)構造体のように初期化する (非推奨) #include <iostream> using namespace std; const int MAX_STR = 16; class MyClass { public: int m_integer; char m_str[MAX_STR + 1]; void Show(); }; void MyClass::Show...
