扩点最短路
扩点最短路
不把实际位置看作图上的点，而是把实际位置和该位置的所有状态的组合看作是图上的点，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;
}
// BFS
int 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});
}
}
}
}