题目描述

在一个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

这道题需要：
1. 使用 Dijkstra 求每个景点到其他地方的最短路
2. 用 DFS 枚举访问景点的顺序，统计答案
3.
注意这道题的点数是 $n \times m$，边数约等于 $4 \times n \times m$

算法1

(Dijkstra朴素版) $O((n \times m)^2 \times 10)$

用最多10次Dijkstra朴素版求出每个景点与其他所有区域的最短路
求完后用dfs枚举参观顺序，统计答案

朴素版Dijkstra时间复杂度为 点数^2，这道题点数是10000, 所以会超时
正解看下面

算法2

(Dijkstra堆优化版) $O((n \times m) \log (n \times m))$

用最多10次Dijkstra堆优化版求出每个景点与其他所有区域的最短路
求完后用dfs枚举参观顺序，统计答案

这道题点数是10000, 10000 log 10000 不会超时

AC 代码（C++）

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;

const int N = 100010, M = 400010, INF = 9e18;
int n, m, p;
int h[N], e[M], w[M], ne[M], idx, mp[105][105];
int q[N], dist[105][N];
int source[105];
bool st[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int T(int x, int y) {          // 把横纵坐标转换为编号
    return m * (x - 1) + y;        
}

void dijkstra(int start, int dist[]) {      // 堆优化版Dijkstra
    memset(dist, 0x3f, N);
    dist[start] = 0;
    memset(st, 0, sizeof st);
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, start});
    while (heap.size()) {
        auto t = heap.top();
        heap.pop();
        int ver = t.second;
        if (st[ver]) continue;
        st[ver] = true;
        for (int i = h[ver]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i]) {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

int dfs(int u, int start, int distance) {
    if (u > p) return distance;
    int res = INF;
    for (int i = 1; i <= p; i ++ ) {
        if (!st[i]) {
            st[i] = true;
            res = min(res, dfs(u + 1, i, distance + dist[start][source[i]]));
            st[i] = false;
        }
    }
    return res;
}

signed main() {
    memset(h, -1, sizeof(h));
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> mp[i][j];
    for (int i = 1; i < n; i++)
        for (int j = 1; j <= m; j++)
            add(T(i, j), T(i, j) + m, (mp[i][j] - mp[i + 1][j]) * (mp[i][j] - mp[i + 1][j]) + 1),
                add(T(i, j) + m, T(i, j), (mp[i][j] - mp[i + 1][j]) * (mp[i][j] - mp[i + 1][j]) + 1);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j < m; j++)
            add(T(i, j), T(i, j) + 1, (mp[i][j] - mp[i][j + 1]) * (mp[i][j] - mp[i][j + 1]) + 1),
                add(T(i, j) + 1, T(i, j), (mp[i][j] - mp[i][j + 1]) * (mp[i][j] - mp[i][j + 1]) + 1);
    n *= m;
    cin >> p;
    source[0] = 1;
    for (int i = 1; i <= p; i++) {
        int a, b;
        cin >> a >> b;
        source[i] = T(a, b);
    }
    for (int i = 0; i <= p; i++) dijkstra(source[i], dist[i]);
    memset(st, 0, sizeof st);
    cout << dfs(1, 0, 0);
    return 0;
}