代码随想录算法训练营第六十二天 | 图论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;// 开始计算Fnext.g = k.g + 5; // 统一不开根号，这样可以提高精度，马走日，1 * 1 + 2 * 2 = 5next.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();
}