提交记录 7994


用户 题目 状态 得分 用时 内存 语言 代码长度
Jouna_Kasa_Hasinele noip17e. 【NOIP2017】宝藏 Accepted 100 139.302 ms 32 KB C++ 1.04 KB
提交时间 评测时间
2019-01-26 21:46:55 2020-08-01 01:11:29
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=15,K=(1<<12)+5,INF=0x3f3f3f3f;
int n,m,u,v,ww,ans=INF;
int f[K],d[N],g[N][N];
inline void dfs(int now)
{
    if(now==(1<<n)-1)
        return;
    for(int i=1;i<=n;i++)
    {
        if((now&(1<<i-1))==0)
            continue;
        for(int j=1;j<=n;j++)
        {
            if(g[i][j]==INF)
                continue;
            if(now&(1<<j-1))
                continue;
            d[j]=d[i]+1;
            if(f[now|(1<<j-1)]>f[now]+g[i][j]*d[j])
            {
                f[now|(1<<j-1)]=f[now]+g[i][j]*d[j];
                dfs(now|(1<<j-1));
            }
            d[j]=0;
        }
    }
}
int main()
{
    memset(g,0x3f,sizeof(g));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&ww);
        g[u][v]=g[v][u]=min(g[u][v],ww);
    }
    for(int i=1;i<=n;i++)
    {
        memset(f,0x3f,sizeof(f));
        f[1<<i-1]=0;
        dfs(1<<i-1);
        ans=min(ans,f[(1<<n)-1]);
    }
    printf("%d\n",ans);
    return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #110.2 us32 KBAcceptedScore: 5

Testcase #217.34 us32 KBAcceptedScore: 5

Testcase #326.19 us32 KBAcceptedScore: 5

Testcase #441.45 us32 KBAcceptedScore: 5

Testcase #5170.31 us32 KBAcceptedScore: 5

Testcase #6137.61 us32 KBAcceptedScore: 5

Testcase #745.14 us32 KBAcceptedScore: 5

Testcase #8120.61 us32 KBAcceptedScore: 5

Testcase #970.9 us32 KBAcceptedScore: 5

Testcase #1079.39 us32 KBAcceptedScore: 5

Testcase #11198 us32 KBAcceptedScore: 5

Testcase #12189.22 us32 KBAcceptedScore: 5

Testcase #13706.92 us32 KBAcceptedScore: 5

Testcase #14768.7 us32 KBAcceptedScore: 5

Testcase #1527.773 ms32 KBAcceptedScore: 5

Testcase #1637.045 ms32 KBAcceptedScore: 5

Testcase #1768.879 ms32 KBAcceptedScore: 5

Testcase #18109.575 ms32 KBAcceptedScore: 5

Testcase #19139.302 ms32 KBAcceptedScore: 5

Testcase #20113.513 ms32 KBAcceptedScore: 5


Judge Duck Online | 评测鸭在线
Server Time: 2020-10-29 19:38:18 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用