Travelling

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3905    Accepted Submission(s): 1234

   
   

    
    2 1
1 2 100
3 2
1 2 40
2 3 50
3 3
1 2 3
1 3 4
2 3 10
   
   

   
   

    
    100
90
7 
   
   

DP+状态压缩：每一个点最多仅仅能经过2次，考虑用3进制存储状态；

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 12
#define M 59050
#define LL long long
const int inf=0x1f1f1f1f;  //注意初始化值
int tri[N]= {0,1,3,9,27,81,243,729,2187,6561,19683,59049};
int g[N][N];
int dig[M][N]; //dig[i][j]记录I状态下J点是否出现，出现几次
int dp[M][N]; //dp[s][j] 在状态s下，以j为终点的最短距离
void inti()     //求出每一个状态s相应的3进制位的信息
{
    int i,j,t;
    for(i=1;i<M;i++)
    {
        for(t=i,j=1;j<=10;j++)
        {
            dig[i][j]=t%3;          //求出该状态下到达每一个的城市次数
            t/=3;
            if(!t) break;
        }
    }
}
int main()
{
    int i,j,a,b,c;
    int n,m,s;
    inti();
    while(scanf("%d%d",&n,&m)!=-1)
    {
        memset(g,inf,sizeof(g));
        memset(dp,inf,sizeof(dp));
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            g[a][b]=g[b][a]=min(c,g[a][b]);
        }
        for(i=1;i<=n;i++)      //起始状态。能够任一城市为起点。
            dp[tri[i]][i]=0;   //距离自然初始化为0
        int ans=inf;
        for(s=1;s<tri[n+1];s++)  //在s状态以i为终点时更新其它状态的值
        {
            int f=1;
            for(i=1;i<=n;i++)
            {
                if(dig[s][i]==0)     //推断当前状态S下，每一个城市是否都已到达
                    f=0;
                if(dp[s][i]==inf)
                    continue;
                for(j=1;j<=n;j++) //dp[s][i]状态到dp[s+tri[j]][j]状态
                {
                    if(g[i][j]==inf||i==j||dig[s][j]>=2)
                        continue;
                    int news=s+tri[j];
                    dp[news][j]=min(dp[news][j],dp[s][i]+g[i][j]);
                }
            }
            if(f)  
                for(i=1;i<=n;i++)
                ans=min(ans,dp[s][i]);
        }
        if(ans==inf)
            ans=-1;
        printf("%d\n",ans);
    }
    return 0;
}

</pre><p></p><p></p><p><span style="font-size:18px; color:#33ccff">bfs+状态压缩：</span></p><p><span style="color:rgb(51,204,255); font-size:18px">開始时把每个点都入队，模拟3进制处理每个状态，最后+优化。
</span></p><p></p><pre code_snippet_id="479354" snippet_file_name="blog_20141004_2_7195338" name="code" class="cpp">#include<iostream>#include<stdio.h>#include<math.h>#include<string.h>#include<algorithm>#include<iostream>#include<queue>using namespace std;#define N 12#define LL long longconst int inf=0x3fffffff;int g[N][N];int n,m,ans;int mark[N][60000];struct node{    int x,t,s,cnt;  //位置、时间、状态、个数    friend bool operator<(node a,node b)    {        return a.t>b.t;    }};int gettmp(int x,int k)  //得到X在3进制下的第K位是多少{                        //推断该点是否经过了。经过了几次    int t;    while(x)    {        t=x%3;        k--;        if(k==0)            break;        x/=3;    }    return k?0:t;}void inti()      //初始化数组{    int i,j;    for(i=1;i<=n;i++)    {        for(j=0;j<(int)pow(3,n);j++)            mark[i][j]=inf;    }}void bfs(){    int i;    priority_queue<node>q;    node cur,next;    for(i=1;i<=n;i++)    {        cur.x=i;        cur.s=pow(3,(i-1));        cur.t=0;        cur.cnt=1;        q.push(cur);        mark[i][0]=0;    }    while(!q.empty())    {        cur=q.top();        q.pop();        for(i=1;i<=n;i++)        {            if(g[cur.x][i]==inf)  //此路不通                continue;            next.cnt=cur.cnt;            next.s=cur.s;            next.t=cur.t+g[cur.x][i];            if(ans<next.t)    //优化非常重要                continue;            next.x=i;            int t=gettmp(next.s,i);  //该点经过了几次，            if(t>=2)                 //经过2次后就不能走了                continue;            next.s+=pow(3,(i-1));    //该点经过次数加一            if(t==0)                 //经过一个新景点            {                next.cnt++;                if(next.cnt==n)                {                    ans=min(ans,next.t);                    continue;                }            }            if(next.t<mark[i][next.s])            {                mark[i][next.s]=next.t;                q.push(next);            }        }    }}int main(){    int a,b,c,i,j;    while(scanf("%d%d",&n,&m)!=-1)    {        for(i=0;i<=n;i++)            for(j=1;j<=n;j++)                g[i][j]=(i==j?
0:inf);        for(i=0;i<m;i++)        {            scanf("%d%d%d",&a,&b,&c);            g[a][b]=g[b][a]=min(g[a][b],c);        }        ans=inf;        inti();        bfs();        if(ans==inf)            ans=-1;        printf("%d\n",ans);    }    return 0;}