WA60分求调

常规
1

有谁能帮忙一下呀？

image

60分代码

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N=110;
vector<pair<int,int>> edge[100010];
int st[100010],dist[100010][N],ar[N][N],n,m,p;
int vis[20],kr[20];
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
int maxn=-1e18,minn=1e18;
int tmp[100010];
void dfs(int k){
	if(k==p+1){
		int ans=0,last=1;
		for(int i=1;i<=p;i++){
			ans+=dist[last][tmp[kr[i]]];
			last=tmp[kr[i]];
		}
		minn=min(minn,ans);
		return;
	}
	for(int i=1;i<=p;i++){
		if(vis[i]==0){
			vis[i]=1;
			kr[k]=i;
			dfs(k+1);
			vis[i]=0;
		}
	}
}
void dijkstra(int x){
    for(int i=1;i<=n*m;i++) dist[x][i]=1e18;
    memset(st,0,sizeof st);
    st[x]=0;
    dist[x][x]=0;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
    q.push({0,x});
    while(!q.empty()){
        int a=q.top().second;q.pop();
        if(st[a]) continue;
        st[a]=1;
        for(auto v:edge[a]) if(dist[x][a]+v.second<dist[x][v.first]){
            dist[x][v.first]=dist[x][a]+v.second;
            q.push({dist[x][v.first],v.first});
        }
    }
}

signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>ar[i][j];
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
        int x=(i-1)*m+j;
        for(int k=0;k<4;k++){
            int xx=i+dx[k],yy=j+dy[k];
            if(1<=xx&&xx<=n&&1<=yy&&yy<=m){
                int y=(xx-1)*m+yy;
                edge[x].push_back({y,abs(ar[i][j]-ar[xx][yy])*abs(ar[i][j]-ar[xx][yy])+1});
            }
        }
    }
    cin>>p;
    dijkstra(1);
    for(int i=1;i<=p;i++){
        int x,y;cin>>x>>y;
        int z=(x-1)*m+y;
        tmp[i]=z;
        dijkstra(z);
    }
    dfs(1);
    cout<<minn;
    return 0;
}
2

思路是每个点先用dijkstra算法求最短路，然后用dfs全排列暴力算出做小值即可。

3

看不清题目，可不可以发文字版本？

4

文字版本：

题目描述
在一个N×M的区域中存在有若干个景点（不超过10个），
且每一小区域的海拔高度是高低不一的。假设相临两1×1区域的高度差为x，
则从其中一个区域移到另一区域将耗费x^2+1分钟的时间。
我们要求得到一条由区域（1，1）出发，经过所有景点的路线，并保证花费的时间最短。


输入格式：
输入文件中的第一行为两个整数N，M，表示区域的大小。
接下来N行为一个N×M的矩阵，给出了每个1×1的小区域的海拔高度。其中：第N+2行中为一个数P，表示该区域内的景点个数。而接下来的P行，每行有两个数Xi，Yi，给出了各个景点的位置坐标。
输入文件中相邻两数用一个或多个空格隔开。
输出格式：
输出文件中仅一行为一个数，即最少需耗费的时间。

样例：
4 4
1 9 6 12
8 7 3 5
5 9 11 11
7 3 2 6
2
2 3
4 3

输出：
122
5

数据范围也要发

6

image