代码随想录算法训练营第六十二天 | 图论part11

#include <iostream>
#include <vector>
#include <climits>
#include <fstream>

using namespace std;

void floyd(vector<vector<vector<int>>>& grid) {
    int n = grid.size() - 1;
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                grid[i][j][k] = min(grid[i][j][k - 1],
                    grid[i][k][k - 1] + grid[k][j][k - 1]);
            }
        }
    }
}

int main() {
    ifstream infile("input.txt");
    int n, m;
    int u, v, w;
    cin >> n >> m;
    // grid[i][j][k]代表从i到j且只经过1-k作为中间节点的最小距离
    vector<vector<vector<int>>> grid(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, 10005)));
    while (m--) {
        cin >> u >> v >> w;
        grid[u][v][0] = w;
        grid[v][u][0] = w;
    }
    floyd(grid);
    int q;
    cin >> q;
    int start, end;
    while (q--) {
        cin >> start >> end;
        if (grid[start][end][n] != 10005) cout << grid[start][end][n] << endl;
        else cout << -1 << endl;
    }
}

#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

int dir[8][2] = { -2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2 };

struct Knight {
	int x, y;
	int f, g, h;
	Knight(){}
	Knight(int x, int y) : x(x), y(y) {}
	bool operator < (const Knight& k) const { return k.f < f;}
};

int Heuristic(Knight &k, int b1, int b2) {
	return (k.x - b1) * (k.x - b1) + (k.y - b2) * (k.y - b2);
}

int astar(Knight& start, int b1, int b2) {
	int moves[1001][1001] = { 0 };
	priority_queue<Knight> que;
	que.push(start);
	while (que.size()) {
		Knight k = que.top();
		Knight next;
		que.pop();
		if (k.x == b1 && k.y == b2) return moves[b1][b2];
		for (int i = 0; i < 8; ++i) {
			next.x = k.x + dir[i][0];
			next.y = k.y + dir[i][1];
			if (next.x < 1 || next.x > 1000 || next.y < 1 || next.y > 1000)
				continue;
			if (!moves[next.x][next.y])
			{
				moves[next.x][next.y] = moves[k.x][k.y] + 1;

				// 开始计算F
				next.g = k.g + 5; // 统一不开根号，这样可以提高精度，马走日，1 * 1 + 2 * 2 = 5
				next.h = Heuristic(next, b1, b2);
				next.f = next.g + next.h;
				que.push(next);
			}
		}
	}
	return -1;
}

int main() {
	ifstream infile("input.txt");
	int n;
	cin >> n;
	while (n--) {
		int a1, a2, b1, b2;
		cin >> a1 >> a2 >> b1 >> b2;
		Knight start(a1, a2);
		start.g = 0;
		start.h = Heuristic(start, b1, b2);
		start.f = start.g + start.h;
		cout << astar(start, b1, b2) << endl;
	}
	infile.close();
}