By

动态规划学习（1）

《算法竞赛入门到进阶》学习。

《算法竞赛入门到进阶》

1. 动态规划的概念和思想

DP（Dynamic Programming）是一种算法思想，不是一个特定的算法。

DP与分治法的区别：

  • 分治法是将问题分成独立的子问题，每个子问题能独立解决
  • DP的子问题是相关的，前面子问题的解决结果被后面的子问题使用。

求解DP有 $3$ 步，定义状态、状态转移、算法实现。

2. 基础DP

基础DP是一些经典问题，如递推、01背包、最长公共子序列（LCS）、最长递增子序列（LIS）等。

2.1 硬币问题

2.1.1 最少硬币问题

有 n 种硬币，面值分别为 $v_1,v_2,…,v_n$，数量无限。输入非负整数 s，选硬币使其和为 s。要求输出最少硬币组合。

void solve(){
	int S=251,N=5,s;
	int Min[S],v[5]={1,5,10,25,50};
	memset(Min,0x3f,sizeof(Min));
	Min[0]=0;
	for(int j=0;j<N;j++)
		for(int i=v[j];i<S;i++)
			Min[i]=min(Min[i],Min[i-v[j]]+1);
	cin>>s;
	cout<<Min[s]<<"\n";
}

上述时间复杂度是 $O(SN)$。

2.1.2 打印最少硬币组合

在DP中，除求最优解的数量外，往往还要求输出最优解本身。

在最少硬币问题中，如果要求打印组合方案，需要增加一个记录表 Min_path[i]，记录金额 i 需要的最后一个硬币。利用 Min_path[] 逐步倒推，就能得到所有的硬币。

void prin(int *Min_path,int s){
	while(s){
		cout<<Min_path[s]<<" ";
		s=s-Min_path[s];
	}
}
void solve(){
	int S=251,N=5,s;
	int Min[S],v[5]={1,5,10,25,50};
	int Min_path[S]={0};
	memset(Min,0x3f,sizeof(Min));
	Min[0]=0;
	for(int j=0;j<N;j++)
		for(int i=v[j];i<S;i++){
			if(Min[i]>Min[i-v[j]]+1){
				Min_path[i]=v[i];
				Min[i]=min(Min[i],Min[i-v[j]]+1);
			}
		}
	cin>>s;
	prin(Min_path,s);
}

用数组存储由哪个状态转移而来，即可得到转移路径。

2.1.3 所有硬币组合

有 n 种硬币，面值分别为 $v_1,v_2,…,v_n$，数量无限。输入非负整数 s，选硬币使其和为 s。要求输出所有的硬币组合数量。

如果选取硬币的数量无限：

void solve(){
	int S=251,N=5,s;
	int dp[S]={0},v[5]={1,5,10,25,50};
	dp[0]=1;
	for(int i=0;i<N;i++)
		for(int j=v[i];j<S;j++)
			dp[j]=dp[j]+dp[j-v[i]];
	cin>>s;
	cout<<dp[s]<<"\n";
}

如果选取的硬币数量有限：

void solve(){
	int C=101,M=251;
	int dp[M][C]={0};
	int v[5]={1,5,10,25,50};
	int ans[M]={0};
	dp[0][0]=1;
	for(int i=0;i<5;i++)
		for(int j=1;j<C;j++)
			for(int k=v[i];k<M;k++)
				dp[k][j]+=dp[k-v[i]][j-1];
	for(int i=0;i<M;i++)
		for(int j=0;j<C;j++)
			ans[i]+=dp[i][j];
	int s;
	while(cin>>s)
		cout<<ans[s]<<"\n";
}

2.2 01背包问题

约束条件： \(\sum_{i=1}^{n} w_ix_i≤C ~,~ x_i∈\{0,1\},1≤i≤n\) 目标函数： \(max\sum_{i=1}^{n}v_ix_i\) 基础代码如下：

void solve(){
	int n,m;
	cin>>n>>m;
	int w[n],v[n],dp[n][m+1]={0};
	for(int i=0;i<n;i++) cin>>w[i];
	for(int i=0;i<n;i++) cin>>v[i];
	for(int i=0;i<n;i++){
		for(int j=0;j<=m;j++){
			if(j<v[i]) dp[i][j]=dp[i-1][j];
			else dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
		}
	}
	cout<<dp[n][m]<<"\n";
}

滚动数组覆盖了中间转移状态，只留下了最后的状态，所有损失了很多信息，导致无法输出背包的方案。

滚动数组优化：

void solve(){
	int n,m;
	cin>>n>>m;
	int w[n],v[n],dp[m+1]={0};
	for(int i=0;i<n;i++) cin>>w[i];
	for(int i=0;i<n;i++) cin>>v[i];
	for(int i=0;i<n;i++){
		for(int j=m;j>=v[i];j--){
			dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
		}
	}
	cout<<dp[m]<<"\n";
}

2.3 最长公共子序列（LCS）

最长公共子序列（Longest Common Subsequence）问题：给定两个序列 X 和 Y，找出 X 和 Y 的一个最长公共子序列。

用 $dp[i][j]$ 表示子序列 \(X_i\) 和 \(Y_j\) 的最长公共子序列长度。

当 $X_i=Y_i$ 时，找出 \(X_{i-1}\) 和 \(Y_{i-1}\) 的最长公共子序列，然后在其尾部加上 $X_i$ 即可得到 \(X\) 和 \(Y\) 的最长公共子序列。

当 \(X_i≠Y_i\) 时，最长公共子序列就是 \([X_{i-1},Y_j]\) 的LCS和 \([X_i,Y_{j-1}]\) 的LCS二者中最大值。

void solve(){
	string s1,s2;
	cin>>s1>>s2;
	int dp[s1.size()+1][s2.size()+1]={0};
	for(int i=1;i<=s1.size();i++)
		for(int j=1;j<=s2.size();j++){
			if(s1[i-1]==s2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
			else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
		}
	cout<<dp[s1.size()][s2.size()]<<"\n";
	return ;
}

滚动数组优化：

void solve(){
	string s1,s2;
	cin>>s1>>s2;
	int dp[2][s2.size()+1];
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=s1.size();i++)
		for(int j=1;j<=s2.size();j++){
			if(s1[i-1]==s2[j-1]) dp[i%2][j]=dp[(i-1)%2][j-1]+1;
			else dp[i%2][j]=max(dp[(i-1)%2][j],dp[i%2][j-1]);
		}
	cout<<dp[s1.size()%2][s2.size()]<<"\n";
	return ;
}

这里不能定义 \(int~dp[2][s2.size()+1]=\{0\}\) ，这样dp数组为变长数组（VLA），VLA是C99特性，不是标准C++的一部分，某些编译器（如GCC扩展）可能无法正确初始化。

2.4 最长递增子序列（LIS）

最长递增子序列（Longest Increasing Subsequence）。

第一种方法，将序列排序后与原序列求最长公共子序列即为LIS，复杂度为 \(O(N^2)\)。

void solve(){
	int n;cin>>n;
	int a[n],b[n],dp[2][n+1];
	for(int i=0;i<n;i++) cin>>a[i],b[i]=a[i];
	sort(b,b+n);
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			if(a[i-1]==b[j-1]) dp[i%2][j]=dp[(i-1)%2][j-1]+1;
			else dp[i%2][j]=max(dp[(i-1)%2][j],dp[i%2][j-1]);
		}
	cout<<dp[n%2][n]<<"\n";
}

第二种方法，直接DP求解，状态 \(dp[i]\) 表示以第 \(i\) 个数为结尾的LIS长度，状态转移方程为 \(dp[i]=max\{0,dp[j]\}+1,~0<j<i,A_j<A_i\) ，

答案为 \(max\{dp[i]\}\)，复杂度为 \(O(N^2)\) 。

void solve(){
	int n,ans=0;cin>>n;
	int a[n],dp[n+1];
	for(int i=0;i<n;i++) cin>>a[i];
	memset(dp,0,sizeof(dp));
	for(int i=0;i<n;i++){
		dp[i]=1;
		for(int j=0;j<i;j++)
			if(a[j]<a[i]) dp[i]=max(dp[i],dp[j]+1);
	}
	for(int i=0;i<n;i++) ans=max(ans,dp[i]);
	cout<<ans<<"\n";
}

第三种方法，单调队列，复杂度为 \(O(nlogn)\)。

void solve(){
	int n,ans=0;cin>>n;
	int a[n];
	for(int i=0;i<n;i++) cin>>a[i];
	vector<int> v;
	v.push_back(a[0]);
	for(int i=1;i<n;i++){
		int x=upper_bound(v.begin(),v.end(),a[i])-v.begin();
		if(x==v.size()) v.push_back(a[i]);
		else v[x]=a[i];
	}
	cout<<v.size()<<"\n";
}

3. 递推与记忆化搜索

记忆化搜索，在用递归实现DP时，在递归程序中记录计算过的状态，并在后续的计算中跳过已经算过的重复状态。

在很多情况下，记忆化搜索的逻辑思路和程序比直接写递推更简单。

4.区间DP

区间DP的主要思想是现在小区间进行DP得到最优解，再利用小区间的最优解合并求大区间的最优解。

区间DP的两个难点，枚举所有可能的区间、状态转移方程。

下面用两个经典问题讲解：

4.1 石子合并问题

设有 $N$堆石子排成一排，其编号为 $1,2,3,\cdots,N$。每堆石子有一定的质量 $m_i$。现在要将这 $N$ 堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻。输出最小代价。

状态：\(DP[i][j]\) 为从第 \(i\) 堆石子到第 \(j\) 堆石子的最小花费。

转移方程：\(dp[i][j]=min(dp[i][k]+dp[k+1][j])+sum[i][j],i≤k≤j\)

void solve(){
	int n;cin>>n;
	int m[N],dp[N][N],sum[N];
	sum[0]=0;
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++) 
		cin>>m[i],sum[i]=sum[i-1]+m[i];
	for(int len=1;len<n;len++){
		for(int i=1;i+len<=n;i++){
			int j=i+len;
			dp[i][j]=0x3f3f3f3f;
			for(int k=i;k<=j;k++){
				dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
			}
		}
	}
	cout<<dp[1][n]<<"\n";
}

时间复杂度为 \(O(n^3)\)，只能用来处理规模 \(n<250\) 的问题。

上述三重循环中，前两重循环是枚举所有可能的合并，无法优化，最后一重循环枚举分割点 \(k\) ，是可以优化的。因为每次运行最后一层循环时，都在某个子区间内部寻找最优分割点，该操作在多个子区间是重复的。如果找到这个最优点后保存下来，用于下一次循环，就能避免重复计算。

用 \(s[i][j]\) 表示区间 \([i,j]\) 中的最优分割点，第三重循环可以从区间 \([i,j-1)\) 的枚举优化到区间 \([s[i][j-1],s[i+1][j]]\) 的枚举。其中， \(s[][]\) 的值是在前面的三重循环中找到并记录下来的。符合 “平行四边形优化” 的原理。

void solve(){
	int n;cin>>n;
	int m[N],dp[N][N],sum[N],s[N][N];
	sum[0]=0;
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++) 
		cin>>m[i],sum[i]=sum[i-1]+m[i],s[i][i]=i;
	for(int len=1;len<n;len++){
		for(int i=1;i+len<=n;i++){
			int j=i+len;
			dp[i][j]=0x3f3f3f3f;
			for(int k=s[i][j-1];k<=s[i+1][j];k++){
				if(dp[i][j]>dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]){
					dp[i][j]=dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];
					s[i][j]=k;
				}
			}
		}
	}
	cout<<dp[1][n]<<"\n";
}

优化后，复杂度接近 \(O(n^2)\) ，可以解决 \(n<3000\) 的问题。

4.2 回文串问题

回文串问题：给定一个字符串，然后通过增加和删除部分字符串得到一个回文串，每个字母每种操作代价不同，求最小代价。

定义状态 \(dp[i][j]\) 表示字符串 \(s\) 的子区间 \(s[i,j]\) 变成回文的最小花费。

void solve(){
	int n,m,w[26];
	cin>>m>>n;
	string s;
	cin>>s;s=" "+s;
	while(m--){
		char c;int l,r;
		cin>>c>>l>>r;
		w[c-'a']=min(l,r);
	}
	int dp[N][N]={0};
	for(int len=1;len<n;len++){
		for(int i=1;i<=n-len;i++){
			int j=i+len;
			if(s[i]==s[j]){
				dp[i][j]=dp[i+1][j-1];
			}else dp[i][j]=min(dp[i+1][j]+w[s[i]-'a'],dp[i][j-1]+w[s[j]-'a']);
		}
	}
	cout<<dp[1][n]<<"\n";
}

5. 树形DP

树本身具有 “子结构” 性质，具有递归性，符合DP的性质。

例题1：不相邻最大权值

一颗有根树上的每个结点有一个权值，相邻的父结点和子结点只能选择一个，如何选择使总权值之和最大。

状态：

  • \(dp[i][0]\) 表示不选择 \(i\) 结点时最优解；

  • \(dp[i][1]\) 表示选择 \(i\) 结点时最优解。

转移方程：

  • \[dp[i][0]+=max(dp[son][1],dp[son][0])\]
  • \[dp[i][1]+=dp[son][0]\]
  • 以上 \(son\)，表示子结点，兄弟关系无限制，所以是兄弟求和
#include<bits/stdc++.h>
using namespace std;
const int N=6e3+5;
int value[N],dp[N][2],father[N],n;
vector<int> tree[N];//邻接表
void dfs(int u){
	dp[u][1]=value[u];
	for(int i=0;i<tree[u].size();i++){
		int son=tree[u][i];
		dfs(son);
		dp[u][0]+=max(dp[son][0],dp[son][1]);
		dp[u][1]+=dp[son][0];
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>value[i];
	memset(father,-1,sizeof(father));
	for(int i=1;i<n;i++){
		int a,b;cin>>a>>b;
		tree[b].push_back(a);
		father[a]=b;
	}
	int t=1;
	while(father[t]!=-1) t=father[t];//查找根节点
	dfs(t);
	cout<<max(dp[t][0],dp[t][1])<<"\n";
	return 0;
}

上述遍历每一个结点，复杂度为 \(O(n)\)。

例题2：最远距离

一棵有根树，根节点为 1 ，对其中任意个结点，求最远结点的距离。

状态：

  • \(dp[i][0]\) ：结点 i 的子树到 i 的最长距离
  • \(dp[i][1]\) ：结点 i 的子树到 i 的次长距离
  • \(dp[i][2]\) ：结点 i 往上父节点走的最长距离
#include<bits/stdc++.h>
using namespace std;
const int N=10100;;
struct Node{
	int id;//结点编号
	int cost;//第i结点连接到id结点的边权
};
vector<Node> tree[N];//邻接表
int dp[N][3];
int n;
void init_read(){
	for(int i=1;i<=n;i++) tree[i].clear();
	memset(dp,0,sizeof(dp));
	for(int i=2;i<=n;i++){
		int x,y;cin>>x>>y;
		Node tmp;
		tmp.id=i,tmp.cost=y;//i是x的子结点
		tree[x].push_back(tmp);
	}
}
void dfs1(int u){//dfs,先处理子结点,再处理父结点
	int one=0,two=0;
	for(int i=0;i<tree[u].size();i++){
		//遍历结点father的所有子结点
		Node child=tree[u][i];
		dfs1(child.id);//递归子结点
		int cost=dp[child.id][0]+child.cost;
		//更新最长距离和次长距离
		if(cost>=one){
			two=one;
			one=cost;
		}
		if(cost<one&&cost>two) two=cost;
	}
	dp[u][0]=one;
	dp[u][1]=two;
}
void dfs2(int u){//先处理父结点，再处理子结点
	for(int i=0;i<tree[u].size();i++){
		Node child=tree[u][i];
		if(dp[child.id][0]+child.cost==dp[u][0])//child在最长距离子树上
			dp[child.id][2]=max(dp[u][2],dp[u][1])+child.cost;
		else dp[child.id][2]=max(dp[u][2],dp[u][0])+child.cost;
		dfs2(child.id);
	}
}
int main(){
	while(cin>>n){
		init_read();//初始化，读入
		dfs1(1);//计算dp[][0],dp[][1]
		dp[1][2]=0;
		dfs2(1);//计算dp[][2]
		for(int i=1;i<=n;i++)
			cout<<max(dp[i][0],dp[i][2])<<"\n";
	}
}

6. 数位DP

数位DP：对数字的 “位” 进行与计数有关的DP。

在数位DP中，一般可以使用模板来做这种题型。

状态：\(dp[i][j]\) 表示第 \(i\) 位数中为 \(j\) 的符合要求的数个数

转移方程：\(dp[i][j]= \sum_{k=0}^{9} dp[i-1][k],特殊条件\)

处理完DP数组后，根据给定的范围求答案。

如一个六位数 362415=000000~099999+100000~199999+200000~299999+300000~362415

\[ans=dp[6][0]+dp[6][1]+dp[6][2]+300000 \sim 362415\]

其中 300000~362415又可以看成00000~62415，但是涉及后一位的时候也需要特判。

例题1：不含62和4

在区间 \([m,n]\) 中，不含 62 和 4 的数字个数。

按照上面模板，我们只需要特判第 i 位为 4 或者第 i 位为 6 且上一位为 2 时continue就行了。

#include<bits/stdc++.h>
using namespace std;
int dp[100][10];
void init(){
	dp[0][0]=1;//初始化
	for(int i=1;i<=7;i++){//位数
		for(int j=0;j<=9;j++){//第i位值为j，后面全为0
			for(int k=0;k<=9;k++){//枚举上一位的所有可能值
				if(j==4||j==6&&k==2) continue;
				dp[i][j]+=dp[i-1][k];
			}
		}
	}
}
int solve(int x){//求1~k中有多少符合的数
	int len=0,digit[10],ans=0;
	memset(digit,0,sizeof(digit));
	while(x){
		digit[++len]=x%10;x/=10;
	}
	for(int i=len;i>=1;i--){
		for(int j=0;j<digit[i];j++){
			if(j==4||j==2&&digit[i+1]==6) continue;
			ans+=dp[i][j];
		}
		if(digit[i]==4||digit[i]==2&&digit[i+1]==6) break;
	}
	return ans;
}
int main(){
	int n,m;
	init();
	while(cin>>n>>m){
		if(n==0&&m==0) break;
		cout<<solve(m+1)-solve(n)<<"\n";
	}
	return 0;
}

7.状态压缩DP

每个状态 \(dp[i][j]\) 表示的不是一个数值如花费长度等，而是代表集合的数量，这种处理复杂集合问题的DP叫做状态压缩DP。

集合的状态有很多，往往把方案用二进制数表示，即压缩成二进制。

例题1：Corn Fields G

在一块长方形的土地上，有的格子能种，有的不能种，选择格子种草，草不会相邻，有多少种方案？

状态：\(dp[i][j]\)表示在第 \(i\) 行状态为 \(j\) 的方案数

\(f\) 数组表示DP数组，\(g\) 数组判断状态是否合法，\(F\) 数组表示输入每行可种植状态。9C0E37D6

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int p=100000000;
ll f[13][1<<12],n,m;
ll g[1<<12],a[13][13];
ll F[13];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>a[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			F[i]=(F[i]<<1)+a[i][j];//第i行能种的格子
	for(int i=0;i<(1<<m);i++){//枚举所有状态
		if(!(i&(i>>1))&&!(i&(i<<1))){//第i位左右都没有1
			g[i]=1;
			if((i&F[1])==i) f[1][i]=1;//是第一行的某状态
		}
	}
	for(int x=2;x<=n;x++)
		for(int j=0;j<(1<<m);j++)
			if(((j&F[x-1])==j)&&g[j])//状态可以在上一行&&可行
				for(int k=0;k<(1<<m);k++)
					if(((k&F[x])==k)&&!(j&k)&&g[k]){//状态可以在当行&&与上状态不相邻&&可行
						f[x][k]=(f[x][k]+f[x-1][j])%p;
					}
	int ans=0;
	for(int i=0;i<(1<<m);i++)
		ans=(ans+f[n][i])%p;
	cout<<ans;
	return 0;
}

例题2：旅行商问题（TSP）

有 n 个城市，知道任何两个城市之间的距离，从某城市出发经过每个城市且只经过一次，最后回到出发城市的最少花费。

这是NP难度的，没有多项式时间的高效算法。

状态：

  • \[S:已经访问过的城市集合\]
  • \[v:当前所在城市\]
  • \[dp[S][v]:从v出发访问所有未访问城市且回到起点的最小花费\]

状态转移：

  • \[dp[V][0]=0,V是最后一个城市\]
  • \[dp[S][v]=min(dp[S \cup {u}][u]+dist(v,u)) ,u \notin S\] 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,c[20][20],f[1<<20][20];
//f[城市经过状态][当前所在城市]=从当前城市出发经过未经过城市的费用最小
int main(){
	cin>>n;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			cin>>c[i][j];
	memset(f,0x3f,sizeof(f));//将dp数组赋值很大
	f[(1<<n)-1][0]=0;//全部节点都到达过
	for(int s=(1<<n)-2;s>=0;s--){
		for(int v=0;v<n;v++){
			//枚举当前集合，售货员所在位置
			for(int u=0;u<n;u++){
				if((s>>u)&1) continue;//已经到过u节点
				f[s][v]=min(f[s][v],f[s|(1<<u)][u]+c[v][u]);
				//经过u节点
			}
		}
	}
	cout<<f[0][0];
	return 0;
}

例题3：TSP变形

访问 n 个城市，可以从任意城市开始，每个城市访问的次数不少于1次，不多于2次。n 个城市之间有m条道路，每条道路有花费。最少费用是多少。

在普通TSP中，只有访问和不访问两种状态，这个题有3种情况，可以使用三进制压缩状态。

在下面代码中，\(tri[i][j]\) 表示第 i 个路径，其第 j 位的值是城市状态。

状态：

  • \(dp[i][j]\) ：当前所在城市 i 出发访问所有剩余城市的后回到起点的最小值。

转移：

\[dp[i][j]=min(dp[i][j],dp[k][l]+graph[k][i])\] 
#include<bits/stdc++.h>
using namespace std;
int n,m;
//三进制每位权值
int bit[12]={0,1,3,9,27,81,243,729,2187,6561,19683,59049};
int tri[60000][11];
int dp[11][60000];
int graph[11][11];//存图
void make_trb(){//初始化，所有可能路径
	for(int i=0;i<59050;++i){//共3^10=59049+1种状态
		int t=i;
		for(int j=1;j<=10;++j){
			tri[i][j]=t%3;t/=3;
		}
	}
}
int cmp_dp(){
	int ans=0x3f3f3f3f;
	memset(dp,0x3f,sizeof(dp));
	for(int i=0;i<=n;i++) 
		dp[i][bit[i]]=0;//bit[i]是第i个城市，起点任意
	for(int i=0;i<bit[n+1];i++){
		int flag=1;//所有的城市都遍历过1次以上
		for(int j=1;j<=n;j++){//选一个终点
			if(tri[i][j]==0){//判断终点位是否为0
				flag=0;//还没有经历终点
				continue;
			}
			if(i==j) continue;
			for(int k=1;k<=n;k++){
				int l=i-bit[j];//i状态的第j位置
				if(tri[i][k]==0) continue;
				dp[j][i]=min(dp[j][i],dp[k][l]+graph[k][j]);
			}
		}
		if(flag)//找最小费用
			for(int j=1;j<=n;j++)
				ans=min(ans,dp[j][i]);
	}
	return ans;
}
int main(){
	make_trb();
	while(cin>>n>>m){
		memset(graph,0x3f,sizeof(graph));
		while(m--){
			int a,b,c;cin>>a>>b>>c;
			if(c<graph[a][b]) graph[a][b]=graph[b][a]=c;
		}
		int ans=cmp_dp();
		if(ans==0x3f3f3f3f) cout<<"-1\n";
		else cout<<ans<<"\n";
	}
	return 0;
}