2014
02-26

# Travelling

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.

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 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.

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 

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[60000][11];
int cnt[11][11];
int three[12];
int m,n;
int f[60000][11];
void init()
{
three[1]=1;
for(int i=2;i<=11;i++)
three[i]=three[i-1]*3;
for(int i=0;i<three[11];i++)
{
int tmp=i;
for(int j=1;j<=10;j++)
{
f[i][j]=tmp%3;
tmp/=3;
}
}
}
int main()
{
init();
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(dp,0x7f,sizeof(dp));
memset(cnt,0x7f,sizeof(cnt));
int ans=dp[0][0];
int inf=ans;
int x,y,d;
while(m--)
{
scanf("%d%d%d",&x,&y,&d);
cnt[x][y]=cnt[y][x]=min(cnt[x][y],d);
}
for(int i=1;i<=n;i++)
dp[three[i]][i]=0;
for(int state=1;state<three[n+1];state++)
{
bool ok=1;
for(int i=1;i<=n;i++)
{
if(f[state][i]==0)
ok=0;
if(dp[state][i]==inf)
continue;
for(int j=1;j<=n;j++)
{
if(i==j)
continue;
if(f[state][j]==2)
continue;
if(cnt[i][j]==inf)
continue;
dp[state+three[j]][j]=min(dp[state+three[j]][j],dp[state][i]+cnt[i][j]);
}
}
if(ok)
{
for(int i=1;i<=n;i++)
{
ans=min(ans,dp[state][i]);
}
}
}
if(ans==inf)
ans=-1;
printf("%d\n",ans);
}
return 0;
}

1. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。

2. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

3. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。