Travelling
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2494 Accepted Submission(s): 725
Problem Description
After coding so many days,Mr Acmer wants to have a good rest.So travelling is the best choice!He has decided to visit n cities(he insists on seeing all the cities!And he does not mind which city being his start station because superman
can bring him to any city at first but only once.), and of course there are m roads here,following a fee as usual.But Mr Acmer gets bored so easily that he doesn't want to visit a city more than twice!And he is so mean that he wants to minimize the total fee!He
is lazy you see.So he turns to you for help.
can bring him to any city at first but only once.), and of course there are m roads here,following a fee as usual.But Mr Acmer gets bored so easily that he doesn't want to visit a city more than twice!And he is so mean that he wants to minimize the total fee!He
is lazy you see.So he turns to you for help.
Input
There are several test cases,the first line is two intergers n(1<=n<=10) and m,which means he needs to visit n cities and there are m roads he can choose,then m lines follow,each line will include three intergers a,b and c(1<=a,b<=n),means
there is a road between a and b and the cost is of course c.Input to the End Of File.
there is a road between a and b and the cost is of course c.Input to the End Of File.
Output
Output the minimum fee that he should pay,or -1 if he can't find such a route.
Sample Input
2 1 1 2 100 3 2 1 2 40 2 3 50 3 3 1 2 3 1 3 4 2 3 10
Sample Output
100 90 7
Source
Recommend
gaojie
开始没注意到有重边结果wa了。很简单的一个状态压缩题。
#include <iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int dp[60000][12];//第一维为状态。用三进制表示分别表示访问了0,1,2次
int dis[11][12];//记录两点间距离
int endn[1100];//记录搜索出的最终合法状态
int n,m,cnt;
int INF=0x3f3f3f3f;
void dfs(int p,int v)//搜索合法状态。简单高效
{
int i;
if(p==n)
{
endn[cnt++]=v*3+1;
endn[cnt++]=v*3+2;
return;
}
for(i=1;i<=2;i++)
dfs(p+1,v*3+i);
}
int getk(int x,int k)//获取三进制的第k位
{
int i;
for(i=1; i<k; i++)
x/=3;
return x%3;
}
int addk(int x,int k)//在三进制数第k位加1
{
int i;
int sum=1;
for(i=1; i<k; i++)
sum*=3;
return x+sum;
}
int mi(int a,int b)
{
return a<b?a:b;
}
int main()
{
int i,j,k,limit,now,ans,a,b,c;
while(~scanf("%d%d",&n,&m))
{
memset(dis,0x3f,sizeof dis);
memset(dp,0x3f,sizeof dp);
for(i=0; i<m; i++)
{
scanf("%d%d%d",&a,&b,&c);
if(c<dis[a][b])//注意有重边
dis[a][b]=dis[b][a]=c;
}
getchar();
limit=addk(0,n+1);
cnt=0;
ans=INF;
for(i=1; i<=n; i++)
{
dis[i][i]=0;
dp[addk(0,i)][i]=0;
}
for(i=0; i<limit; i++)
{
for(j=1; j<=n; j++)
{
if(dp[i][j]>=INF)
continue;
for(k=1; k<=n; k++)
{
if(j==k)
continue;
if(dis[j][k]>=INF)
continue;
if(getk(i,k)>=2)
continue;
now=addk(i,k);
dp[now][k]=mi(dp[now][k],dp[i][j]+dis[j][k]);
}
}
}
dfs(1,0);
for(i=0; i<cnt; i++)
for(j=1; j<=n; j++)
ans=mi(ans,dp[endn[i]][j]);
if(ans<INF)
printf("%d\n",ans);
else
printf("-1\n");
}
return 0;
}
/*
5 6
1 2 1
2 3 1
3 4 1
4 5 1
1 3 7
3 5 8
*/
看了下别人的运行时间很短。用到了预处理。值得学习。于是也来了个预处理版。结果比别人还快。估计是我的最终合法状态是搜的不是枚举的缘故吧。
#include <iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int dp[60000][12];//第一维为状态。用三进制表示分别表示访问了0,1,2次
int dis[11][12];//记录两点间距离
int endn[1100];//记录搜索出的最终合法状态
int n,m,cnt;
int INF=0x3f3f3f3f;
int three[15];//记录三进制的数量级
int base[60000][12];//记录三进制个位的数字
void init()//预处理减少预算次数
{
int i,ptr,value;
three[0]=1;
for(i=1;i<11;i++)
three[i]=three[i-1]*3;
memset(base,0,sizeof base);
for(i=0;i<=three[10];i++)
{
ptr=0;
value=i;
while(value)
{
base[i][ptr++]=value%3;
value/=3;
}
}
}
void dfs(int p,int v)//搜索合法状态。简单高效
{
int i;
if(p==n)
{
endn[cnt++]=v*3+1;
endn[cnt++]=v*3+2;
return;
}
for(i=1;i<=2;i++)
dfs(p+1,v*3+i);
}
int mi(int a,int b){ return a<b?a:b; }
int main()
{
int i,j,k,limit,now,ans,a,b,c;
init();
while(~scanf("%d%d",&n,&m))
{
memset(dis,0x3f,sizeof dis);
memset(dp,0x3f,sizeof dp);
for(i=0; i<m; i++)
{
scanf("%d%d%d",&a,&b,&c);
if(c<dis[a][b])
dis[a][b]=dis[b][a]=c;
}
cnt=0;
ans=INF;
limit=three[n];
for(i=1; i<=n; i++)//初始化为。有超人所以第一次到各地为0
{
dis[i][i]=0;
dp[three[i-1]][i]=0;
}
for(i=0; i<limit; i++)//枚举状态
{
for(j=1; j<=n; j++)
{
if(dp[i][j]>=INF)//i状态是到j后的状态才行
continue;
for(k=1; k<=n; k++)//枚举中间值
{
if(j==k)
continue;
if(dis[j][k]>=INF)
continue;
if(base[i][k-1]>=2)
continue;
now=i+three[k-1];
dp[now][k]=mi(dp[now][k],dp[i][j]+dis[j][k]);
}
}
}
dfs(1,0);
for(i=0; i<cnt; i++)
for(j=1; j<=n; j++)
ans=mi(ans,dp[endn[i]][j]);
if(ans<INF)
printf("%d\n",ans);
else
printf("-1\n");
}
return 0;
}
/*
5 6
1 2 1
2 3 1
3 4 1
4 5 1
1 3 7
3 5 8
*/