【题目描述】

山山获得了长沙城内所有景点的门票各一张。然而,长沙城的交通并不发达,只有部分景点

之间有双向道路可供通行。一张门票只能被用一次,因而一个景点只能被经过一次。山山对

景点并不感兴趣,但是对路旁的花草却非常着迷。他希望从 1 号景点出发,走尽量长的路程,

在任意景点结束。你需要告诉他至多能走多长的路。

【输入格式】

第一行两个整数 n m

接下来 m 行,每行三个整数 s t w,表示从 s 号景点到 t 号景点有一条长为 w 的

双向道路。数据保证 s!=t,不保证同一对 s t 只出现一遍

【输出格式】

一行一个整数,表示最长路径长度

【样例输入】

3 3

1 2 1

2 3 2

1 3 4

【样例输出】

6

【数据范围】

100%的数据保证 1 ≤ n ≤ 10; 1 ≤ w ≤ 100

---

 

一开始用的dfs做这题，然后发现不好剪枝，然后就干脆写了状压DP。

其他的都写在注释里了。

代码：

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define ll long long#define il inline#define db double#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))using namespace std;il int gi(){	int x=0,y=1;	char ch=getchar();	while(ch<'0'||ch>'9')		{			if(ch=='-')				y=-1;			ch=getchar();		}  	while(ch>='0'&&ch<='9')		{			x=x*10+ch-'0';			ch=getchar();		}	return x*y;}int dist[145][145];int f[100045][11];//dang qian zai jint main(){	freopen("travel.in","r",stdin);	freopen("travel.out","w",stdout);		int n=gi(),m=gi();		int top=(1<