提交记录 8328


用户 题目 状态 得分 用时 内存 语言 代码长度
LuoshuiTianyi noip17e. 【NOIP2017】宝藏 Accepted 100 90.995 ms 56 KB C++ 1.09 KB
提交时间 评测时间
2019-02-12 19:12:09 2020-08-01 01:16:48
#include<iostream>
#include<cstdio>
using namespace std;
int dis[13],n,m,G[13][13],limit,f[8192],inf=1e9+7,ans=1e9;
void dfs(int x)
{
    for(int i=1;i<=n;i++)
        if((1<<(i-1))&x)
            for(int j=1;j<=n;j++)
                if(((1<<(j-1))&x)==0&&G[i][j]!=inf)
                    if(dis[i]*G[i][j]+f[x]<f[(x|(1<<(j-1)))])
                    {
                        f[x|(1<<(j-1))]=dis[i]*G[i][j]+f[x];
                        int t=dis[j];
                        dis[j]=dis[i]+1;
                        dfs(x|(1<<(j-1)));
                        dis[j]=t;
                    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            G[i][j]=inf;
    limit=(1<<n);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        G[v][u]=G[u][v]=min(G[u][v],min(G[v][u],w));
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            dis[j]=inf;
        for(int j=0;j<limit;j++)
            f[j]=inf;
        f[(1<<(i-1))]=0;
        dis[i]=1;
        dfs(1<<(i-1));
        ans=min(ans,f[limit-1]);
    }
    cout<<ans;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #137.54 us40 KBAcceptedScore: 5

Testcase #247.23 us40 KBAcceptedScore: 5

Testcase #350.78 us40 KBAcceptedScore: 5

Testcase #472.36 us40 KBAcceptedScore: 5

Testcase #5227.88 us40 KBAcceptedScore: 5

Testcase #6160.1 us40 KBAcceptedScore: 5

Testcase #772.23 us40 KBAcceptedScore: 5

Testcase #8146.9 us40 KBAcceptedScore: 5

Testcase #9249.83 us40 KBAcceptedScore: 5

Testcase #10170.56 us40 KBAcceptedScore: 5

Testcase #11237.51 us40 KBAcceptedScore: 5

Testcase #12234.36 us40 KBAcceptedScore: 5

Testcase #13627.68 us40 KBAcceptedScore: 5

Testcase #14714.57 us40 KBAcceptedScore: 5

Testcase #1518.83 ms48 KBAcceptedScore: 5

Testcase #1625.384 ms48 KBAcceptedScore: 5

Testcase #1751.486 ms56 KBAcceptedScore: 5

Testcase #1872.06 ms56 KBAcceptedScore: 5

Testcase #1990.995 ms56 KBAcceptedScore: 5

Testcase #2074.01 ms56 KBAcceptedScore: 5


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