网站北京备案快吗,wordpress英语怎么读,怎样设置个人官方网站,东莞横沥做网站题目链接#xff1a;传送门 题意#xff1a; n个城市m条路。刚開始在点1#xff0c;求把每一个城市都遍历一边最后回到1的花费的最小值。 分析#xff1a; 我们首先须要预处理出随意两个国家之间的最短距离。由于数据范围非常小#xff0c;所以直接用Floyd即可了。之后传送门 题意 n个城市m条路。刚開始在点1求把每一个城市都遍历一边最后回到1的花费的最小值。 分析 我们首先须要预处理出随意两个国家之间的最短距离。由于数据范围非常小所以直接用Floyd即可了。之后我们用f[S][i]表示訪问国家的情况为S当前最后訪问的一个国家是i所须要的最小总油量。当中。S的二进制表示记录了訪问国家的情况S在二进制表示下的第i位无论是从左往右还是从右往左都能够假设是1则表示第i个国家被訪问过了否则表示第i个国家没有被訪问过那么f[S|(1i)][i]min(f[S][j]f[i][j])。当中i和j满足S(1j)1且S(1i)0。最開始时除了f[1][1]是0其它情况都是无穷大之后先枚举S再枚举i我验题的时候由于这里搞反结果WA了。那么终于的答案就是min(f[(1n)-1][i]f[i][1])。当中i∈\in∈ [2,n]。总复杂度为O(n3n2∗2n)O(n^3n^2*2^n)O(n3n2∗2n)。 转自Bestcode。 以下说说我的状态转移首先也处理好了每两个城市之间的最短路。 然后DP[S][J]S转换成二进制后1代表去过,0代表没有去过最后留在J的最小花费然后就枚举S没有去过的城市k DP[S|(1k)][k]min(DP[S][j]mp[j][k]) 代码例如以下 #include iostream
#include cstring
#include algorithm
#include cstdio
using namespace std;const int maxn 18;const int inf 0x3f3f3f3f;int dp[1maxn][maxn];int mp[maxn][maxn];void init(){memset(dp,inf,sizeof(dp));for(int i0;imaxn;i)for(int j0;jmaxn;j)mp[i][j]inf;
}int main()
{int t,n,m;scanf(%d,t);while(t--){init();scanf(%d%d,n,m);for(int i0;im;i){int u,v,w;scanf(%d%d%d,u,v,w);mp[u][v]min(mp[u][v],w);mp[v][u]min(mp[v][u],w);}for(int i0;imaxn;i) mp[i][i]0;for(int k1;kn;k){for(int i1;in;i){for(int j1;jn;j){mp[i][j]min(mp[i][j],mp[i][k]mp[k][j]);}}}dp[1][1]0;for(int i0;i(1n);i){for(int j0;jn;j){if(!(i(1j))){for(int k1;kn;k){dp[i|(1j)][j1]min(dp[i|(1j)][j1],dp[i][k]mp[k][j1]);}}}}int ans inf;for(int i1;in;i)ans min(ans,dp[(1n)-1][i]mp[i][1]);printf(%d\n,ans);}return 0;
}转载于:https://www.cnblogs.com/gccbuaa/p/6939622.html
