国外php网站源码,深圳网站建设公司哪家,昌吉网站建设咨询电话,做海报有什么好的网站推荐郊区春游
题意#xff1a;
给定一张图#xff0c;求从某个起点出发#xff0c;经过其中R个点#xff08;R个点给出#xff09;的最短路径#xff08;每个点经过且只经过一遍#xff09;
题解#xff1a;
首先我们用floyed处理出任意两点的距离 dp[i][j]表示当前状态…郊区春游
题意
给定一张图求从某个起点出发经过其中R个点R个点给出的最短路径每个点经过且只经过一遍
题解
首先我们用floyed处理出任意两点的距离 dp[i][j]表示当前状态为i当前所在的目标城市为j的最短路径 i为01串1表示该点走过0表示没走过 从点x到点y 城市x已经走过城市x是编号j的所以i(1j) 1,i的第j位是1说明x走过 y还未走所以(i(1k)) 0i的第k位是0说明y还没走下一步可以走 转移方程:
dp[i(1k)][k]min(dp[i(1k)][k],dp[i][j]dist[x][y]);代码
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b)
typedef long long ll;
using namespace std;inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int inf0x3f3f3f;
const int maxn210;
int dp[41000][17];
int dis[maxn][maxn];
int a[maxn];
int main()
{memset(dis,inf,sizeof(dis));memset(dp,inf,sizeof dp);int n,m,r;cinnmr;for(int i0;ir;i)cina[i];for(int i1;im;i){int x,y,w;cinxyw;dis[x][y]dis[y][x]w;}for(int i1;in;i){for(int j1;jn;j){for(int k1;kn;k){if(ij||jk||ik)continue;dis[j][k]min(dis[j][k],dis[j][i]dis[i][k]);}}}for(int i0;ir;i)dp[1i][i]0;//设置起点 int x,y;for(int i1;i(1r);i)//枚举所有状态{for(int j0;jr;j)//枚举出发点 {if(!(i(1j)))continue;//如果j没走过 xa[j];for(int k0;kr;k)//枚举到达点 {if(i(1k))continue;//如果k还未走过 ya[k];dp[i|(1k)][k]min(dp[i|(1k)][k],dp[i][j]dis[x][y]);}}}int minxinf;for(int i0;ir;i)minxmin(minx,dp[(1r)-1][i]);//(1r)-1表示r个点都经过的情况coutminx;
}
