[hdu3001]Travelling
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7817 Accepted Submission(s):
2553
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.
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.
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.
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.
Output
Output the minimum fee that he should pay,or -1 if he
can't find such a route.
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
题目大意：有N个点，M条边，每条边都有权值，每个点不能经过大于两次，问把整个图走完的最小代价。如果不行输出-1。
试题分析：这题不同于codevs上那道3分钟的TSP水题，这回对于次数有限制。
考虑2进制，我们发现无法表示它的状态了，那么3进制可行么？
3进制每位代表访问过这个节点的次数。dp[S][j]表示状态为S，现在在j的最小代价。
那么dp[S][j]=min(dp[S][j],dp[S-tri[j]][k]+e[k][j]);
tri[i]表示三进制下长度为i的MAX。
我们可以先预处理出来3进制每个数每位是什么，然后就好做了。
代码（为什么就我写的是逆推QAQ）：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std; inline int read(){
int x=0,f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
const int MAXN=100001;
const int INF=0x1f1f1f1f;//这里不知道为什么赋值9999999过不了
const int Max3=59050;
int tri[12] ={0,1,3,9,27,81,243,729,2187,6561,19683,59049};
int N,M;
int ditk[100001][11];
int dp[100001][11];
int e[11][11]; int ans; int main(){
memset(ditk,0,sizeof(ditk));
for(int i=1;i<Max3;i++){
int tmp=0,x=i;
while(x){
ditk[i][++tmp]=x%3;
x/=3;
if(x==0) break;
}
}
while(scanf("%d%d",&N,&M)!=EOF){
ans=INF;
memset(dp,INF,sizeof(dp));
memset(e,INF,sizeof(e));
for(int i=1;i<=M;i++){
int u=read(),v=read(),w=read();
e[u][v]=e[v][u]=min(w,e[v][u]);
}
for(int i=1;i<=N;i++) dp[tri[i]][i]=0;
for(int i=1;i<tri[N+1];i++){
bool k=true;
for(int j=1;j<=N;j++){
if(!dp[i][j]) continue;
if(!ditk[i][j]) continue;
for(int k=1;k<=N;k++){
if(e[k][j]>=INF||ditk[i-tri[j]][j]>=2||k==j||!ditk[i-tri[j]][k]) continue;
dp[i][j]=min(dp[i][j],dp[i-tri[j]][k]+e[k][j]);
}
}
}
for(int i=1;i<tri[N+1];i++){
bool k=true;
for(int j=1;j<=N;j++) if(!ditk[i][j]){
k=false; break;
}
if(k) for(int j=1;j<=N;j++) ans=min(ans,dp[i][j]);
}
if(ans!=INF) printf("%d\n",ans);
else puts("-1");
}
}
又写了一个顺推：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std; inline int read(){
int x=0,f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
const int MAXN=100001;
const int INF=0x1f1f1f1f;
const int Max3=59050;
int tri[12] ={0,1,3,9,27,81,243,729,2187,6561,19683,59049};
int N,M;
int ditk[100001][11];
int dp[100001][11];
int e[11][11]; int main(){
memset(ditk,0,sizeof(ditk));
for(int i=0;i<Max3;i++){
int tmp=0,x=i;
while(x){
ditk[i][++tmp]=x%3;
x/=3;
if(x==0) break;
}
}
while(scanf("%d%d",&N,&M)!=EOF){
int ans=INF;
memset(dp,INF,sizeof(dp));
memset(e,INF,sizeof(e));
for(int i=1;i<=M;i++){
int u=read(),v=read(),w=read();
if(w<e[u][v]) e[u][v]=e[v][u]=w;
}
for(int i=1;i<=N;i++) dp[tri[i]][i]=0;
for(int i=0;i<tri[N+1];i++){
bool flagt=true;
for(int j=1;j<=N;j++){
if(!ditk[i][j]) flagt=false;
if(dp[i][j]==INF) continue;
for(int k=1;k<=N;k++){
if(k==j) continue;
if(e[j][k]>=INF||ditk[i][k]>=2) continue;
dp[i+tri[k]][k]=min(dp[i+tri[k]][k],dp[i][j]+e[j][k]);
}
}
if(flagt){
for(int j=1;j<=N;j++)
ans=min(ans,dp[i][j]);
}
}
if(ans==INF) puts("-1");
else printf("%d\n",ans);
}
}