Loading...

NOIP2017 宝藏

check评论:0 条 remove_red_eye浏览量:298 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-05-13

这道题听说正解是dp
完了我不会啊qwq
怎么办啊qwq
我好菜啊qwq
于是手写一发暴力,预计得分70
实际得分100
qwq好感动啊
qwq数据这么水真的好吗
code:

#include <bits/stdc++.h>
using namespace std;
#define INF 2147483647
int n,m,g[20][20],f[10000],dis[20],ans=INF;
void find(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(f[x|(1<<(j-1))]>f[x]+dis[i]*g[i][j])
                    {
                        int tmp=dis[j];
                        dis[j]=dis[i]+1;
                        f[x|(1<<(j-1))]=f[x]+dis[i]*g[i][j];
                        find(x|(1<<(j-1)));
                        dis[j]=tmp;
                    }
                }
            }
        }
    }  
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    g[i][j]=INF;
    int u,v,z;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&z);
        g[u][v]=min(g[u][v],z);
        g[v][u]=min(g[v][u],z);
    }
    for(int o=1;o<=n;o++)
    {
        for(int i=1;i<=n;i++) 
        {
            dis[i]=INF;
        }
        for(int i=1;i<=(1<<n)-1;i++) 
        {
            f[i]=INF;
        }
        dis[o]=1;
        f[1<<(o-1)]=0;
        find(1<<(o-1));
        ans=min(ans,f[(1<<n)-1]);
    } 
    printf("%d",ans);
    return 0;
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名