路线题解
题目描述
在一个 N×M 的区域中存在有 P 个景点（ 0<P\le10 ），且每一小区域的海拔高度是高低不一的。假设相临两 1×1 区域的高度差为 x ，则从其中一个区域移到另一区域将耗费 x^2+1 分钟的时间。我们要求得到一条由区域 (1,1) 出发，经过所有景点的路线，并保证花费的时间最短。
思路分析
题目意思并不难，要求是求遍历完所以景点的花费最小值，因为是多个景点，所以直接用 DFS,BFS 极其麻烦,所以第一步便是对每个景点跑一边 Dijkstra ，对两点之间进行建边，时间复杂度为 O(P~NM~logNM ), 然后就转换成了非常经典旅行商问题，这时候搜索的话时间复杂度会达到 O(P!) ，非常的卡。所以正解就是非常经典的状压dp，时间复杂度为 O(2^PP^2) 。
dp[i][S] 表示以 i 为终点，已访问结点集合为 S (用二进制表示， 1 表示已经访问过， 0 表示未访问)的最短路径
转移方程： dp[i][S]=min(dp[i][S],dp[j][S~XOR~(1<<(j-1))]+dis[j][i])
初始化： dp[i][1<<(i-1)]=dis[0][i]
答案： min~(dp[i][(1<<p)-1])
这是很基础的状压dp，不会的快去补课（状压dp
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,m,p,a[N][N],dis[N][N],vis[N][N];
int dx[6]={-1,0,1,0},dy[6]={0,1,0,-1};
int d[15][15];
struct node{
int dis,x,y;
node(){}
node(int Dis,int X,int Y){dis=Dis,x=X,y=Y;}
bool operator >(const node a)const{return dis>a.dis;}
};
struct spot{
int x,y;
}sp[15];
priority_queue<node,vector<node>,greater<node> >q;
void dijkstra(int sx,int sy){
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
dis[i][j]=INT_MAX;
vis[i][j]=0;
}
}
dis[sx][sy]=0;
q.push(node(0,sx,sy));
while(!q.empty()){
node nw=q.top();
q.pop();
if(vis[nw.x][nw.y]) continue;
vis[nw.x][nw.y]=1;
for(int i=0;i<4;i++){
int x=nw.x+dx[i],y=nw.y+dy[i];
if(x<1||x>n||y<1||y>m) continue;
int w=(a[nw.x][nw.y]-a[x][y])*(a[nw.x][nw.y]-a[x][y])+1;
if(dis[x][y]>dis[nw.x][nw.y]+w){
dis[x][y]=dis[nw.x][nw.y]+w;
q.push(node(dis[x][y],x,y));
}
}
}
}
int dp(){
int dp[15][1<<11];
memset(dp,0x3f,sizeof(dp));
for(int i=1;i<=p;i++){
dp[i][1<<(i-1)]=d[0][i];
}
for(int s=1;s<=(1<<p)-1;s++){
for(int i=1;i<=p;i++){
if(s&(1<<(i-1))){
for(int j=1;j<=p;j++){
if((s&(1<<(j-1)))&&i!=j){
dp[i][s]=min(dp[i][s],dp[j][s^(1<<(i-1))]+d[i][j]);
}
}
}
}
}
int ans=INT_MAX;
for(int i=1;i<=p;i++){
ans=min(ans,dp[i][(1<<(p))-1]);
}
return ans;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
cin>>p;
for(int i=1;i<=p;i++){
cin>>sp[i].x>>sp[i].y;
}
dijkstra(1,1);
for(int i=1;i<=p;i++){
d[0][i]=dis[sp[i].x][sp[i].y];
}
for(int i=1;i<=p;i++){
dijkstra(sp[i].x,sp[i].y);
for(int j=i+1;j<=p;j++){
d[i][j]=d[j][i]=dis[sp[j].x][sp[j].y];
}
}
cout<<dp();
return 0;
}
彩蛋：
