扩点最短路
不把实际位置看作图上的点，而是把实际位置和该位置的所有状态的组合看作是图上的点，BFS 或者 Dijkstra 的过程不变，只是增加了一些点。
864. 获取所有钥匙的最短路径
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>using namespace std;class Solution {
public:int rows, columns;// 最多 6 把钥匙int max_k = 6;int key = 0;vector<int> move{-1, 0, 1, 0, -1};bool isCoordinateLegal(int row, int column) {return row >= 0 && row < rows && column >= 0 && column < columns;}// BFSint shortestPathAllKeys(vector<string> &grid) {rows = grid.size();columns = grid[0].size();// (x, y, 持有钥匙的状态)queue<vector<int>> q;// 找起点for (int i = 0; i < rows; ++i) {for (int j = 0; j < columns; ++j) {if (grid[i][j] == '@') {q.emplace(vector<int>{i, j, 0});} else if (grid[i][j] >= 'a' && grid[i][j] <= 'f') {// 计算获得所有钥匙的最终状态key |= (1 << (grid[i][j] - 'a'));}}}// 表示当前位置的某个状态是否从队列中弹出过，状态是指持有钥匙的情况vector<vector<vector<bool>>> visited(rows, vector<vector<bool>>(columns));for (int i = 0; i < rows; ++i)for (int j = 0; j < columns; ++j)visited[i][j].resize(key, false);int step = 1;while (!q.empty()) {int size = q.size();// 逐层弹出for (int i = 0; i < size; ++i) {auto f = q.front();q.pop();int x = f[0];int y = f[1];// 经过(x, y)后，到达下个点前持有钥匙的状态int s = f[2];// 四周for (int j = 0; j < 4; ++j) {int nx = x + move[j];int ny = y + move[j + 1];// 越界if (!isCoordinateLegal(nx, ny)) continue;char ch = grid[nx][ny];// 墙if (ch == '#') continue;// 锁，且没对应钥匙if (ch >= 'A' && ch <= 'F' && (s & (1 << (ch - 'A'))) == 0) continue;// 钥匙，更新持有的钥匙状态int ns = s;if (ch >= 'a' && ch <= 'f')ns |= (1 << (ch - 'a'));// 获得所有钥匙了if (ns == key) return step;if (visited[nx][ny][ns]) continue;visited[nx][ny][ns] = true;q.emplace(vector<int>{nx, ny, ns});}}step++;}return -1;}
};
LCP 35. 电动车游城市
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>using namespace std;class Solution {
public:struct cmp {bool operator()(vector<int> &v1, vector<int> &v2) {return v1[2] > v2[2];}};int electricCarPlan(vector<vector<int>> &paths, int cnt, int start, int end, vector<int> &charge) {int n = charge.size();vector<vector<pair<int, int>>> graph(n);// 无向图for (const auto &item: paths) {graph[item[0]].emplace_back(make_pair(item[1], item[2]));graph[item[1]].emplace_back(make_pair(item[0], item[2]));}// (点, 到这个点的剩余电量, 代价)priority_queue<vector<int>, vector<vector<int>>, cmp> heap;// vector[i][j] 为到达 i 点时剩余 j 电量的最小代价vector<vector<int>> distance(n, vector<int>(cnt + 1, INT_MAX));// 访问标记vector<vector<bool>> visited(n, vector<bool>(cnt + 1, false));heap.emplace(vector<int>{start, 0, 0});distance[start][0] = 0;while (!heap.empty()) {auto top = heap.top();heap.pop();int position = top[0];int power = top[1];int cost = top[2];// 结束if (position == end) return cost;if (visited[position][power]) continue;visited[position][power] = true;// 充一格电，到图中扩出来的点，也就是这个点的其他状态if (power < cnt&& !visited[position][power + 1]&& (cost + charge[position] < distance[position][power + 1])) {distance[position][power + 1] = cost + charge[position];heap.emplace(vector<int>{position, power + 1, distance[position][power + 1]});}// 不充电，直接去别的点for (const auto &item: graph[position]) {int nextPosition = item.first;int restPower = power - item.second;int nextCost = cost + item.second;// 到不了下个点，或者下个状态已经弹出过，就跳过if (restPower < 0 || visited[nextPosition][restPower]) continue;if (nextCost < distance[nextPosition][restPower]) {distance[nextPosition][restPower] = nextCost;heap.emplace(vector<int>{nextPosition, restPower, nextCost});}}}return -1;}
};
P4568 [JLOI2011] 飞行路线
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>using namespace std;int n, m, k, s, t;vector<int> head;
vector<int> nxt;
vector<int> to;
vector<int> weight;
int cnt;void build() {head.resize(n, 0);fill(head.begin(), head.end(), 0);nxt.resize((m << 1) + 1);to.resize((m << 1) + 1);weight.resize((m << 1) + 1);cnt = 1;
}void addEdge(int u, int v, int w) {nxt[cnt] = head[u];to[cnt] = v;weight[cnt] = w;head[u] = cnt;cnt++;
}struct cmp {bool operator()(vector<int> &v1, vector<int> &v2) {return v1[2] > v2[2];}
};int main() {cin >> n >> m >> k >> s >> t;build();for (int i = 0, u, v, w; i < m; ++i) {cin >> u >> v >> w;addEdge(u, v, w);addEdge(v, u, w);}// distance[i][j] 为到达 i 点，剩余免费乘坐次数 j 次的最少代价vector<vector<int>> distance(n, vector<int>(k + 1, 0x7fffffff));// 访问标记vector<vector<bool>> visited(n, vector<bool>(k + 1, false));// (点，到点后剩余的免费次数，最少代价)priority_queue<vector<int>, vector<vector<int>>, cmp> heap;distance[s][k] = 0;heap.emplace(vector<int>{s, k, 0});while (!heap.empty()) {auto top = heap.top();heap.pop();int u = top[0];int free = top[1];int cost = top[2];// 结束if (u == t) {cout << cost;return 0;}if (visited[u][free]) continue;visited[u][free] = true;for (int ei = head[u]; ei > 0; ei = nxt[ei]) {int v = to[ei];int w = weight[ei];// 使用一张票if (free > 0&& !visited[v][free - 1]&& cost < distance[v][free - 1]) {distance[v][free - 1] = cost;heap.emplace(vector<int>{v, free - 1, cost});}// 不使用if (!visited[v][free]&& cost + w < distance[v][free]) {distance[v][free] = cost + w;heap.emplace(vector<int>{v, free, cost + w});}}}
}
