Submission #12223

ソースコード

#include<iostream>
using namespace std;
int d[11][11],n,m,s,a,b,c,dp[2048][11],M=1e9;
main()
{
        cin>>n>>m>>s;
        for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i-j)d[i][j]=1e8;
        for(int i=1;i<=m;i++)
        {
                cin>>a>>b>>c;
                d[a][b]=d[b][a]=c;
        }
        for(int k=1;k<=n;k++)
                for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
        for(int i=0;i<1<<n;i++)for(int j=1;j<=n;j++)dp[i][j]=1<<28;
        dp[1<<s-1][s]=0;
        for(int i=1<<s-1;i<1<<n;i++)
        {
                for(int j=1;j<=n;j++)
                {
                        for(int k=1;k<=n;k++)
                        {
                                if(i&1<<k-1)continue;
                                dp[i|1<<k-1][k]=min(dp[i|1<<k-1][k],dp[i][j]+d[j][k]);
                        }
                }
        }
        for(int i=1;i<=n;i++)M=min(M,(dp[(1<<n)-1][i]==-1?1<<28:dp[(1<<n)-1][i])+d[i][s]);
        cout<<M<<endl;
}

ステータス

項目	データ
問題	0010 - クッキー
ユーザー名	kotatsugame
投稿日時	2017-01-29 02:57:56
言語	C++11
状態	Accepted
得点	35
ソースコード長	741 Byte
最大実行時間	23 ms
最大メモリ使用量	516 KB

セット

	セット	得点	Cases
1	小課題１	5 / 5	cookies_input1.txt
2	小課題２	10 / 10	cookies_input2.txt
3	小課題３	20 / 20	cookies_input3.txt

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
cookies_input1.txt	AC	23 ms	476 KB	1
cookies_input2.txt	AC	16 ms	456 KB		2
cookies_input3.txt	AC	18 ms	516 KB			3