大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
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;}
版权声明:本文博客原创文章,博客,未经同意,不得转载。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117246.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...