带费用限制的最短路径SPFA+优先队列
poj1724
ROADS
时间限制: 1000MS | 内存限制: 65536K
总提交数: 10751 | 已通过: 3952
描述
有N个编号为1到N的城市，它们之间由单向道路连接。每条道路有两个参数：长度和过路费（以硬币数量表示）。 Bob和Alice原本住在城市1。由于发现Alice在他们常玩的纸牌游戏中作弊，Bob与她分手并决定搬到城市N。他希望尽快到达那里，但手头资金有限。
我们需要帮助Bob找到从城市1到城市N的一条路径，使得总费用不超过他拥有的硬币数K，并且路径总长度最短。
输入格式
- 第一行包含整数K（0 ≤ K ≤ 10000），表示Bob最多可以支付的硬币数。
- 第二行包含整数N（2 ≤ N ≤ 100），表示城市的总数。
- 第三行包含整数R（1 ≤ R ≤ 10000），表示道路总数。
- 接下来R行中，每行四个整数S、D、L、T，分别表示：
- S：起点城市（1 ≤ S ≤ N）
- D：终点城市（1 ≤ D ≤ N）
- L：道路长度（1 ≤ L ≤ 100）
- T：过路费（0 ≤ T ≤ 100）
输出格式
输出一行，包含一个整数，表示在费用不超过K的前提下，从城市1到城市N的最短路径长度。如果不存在这样的路径，则输出-1。
样例输入
5
6
7
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2
样例输出
11
题意说明
本题看似是典型的双约束最短路问题，即先使费用最小，再在费用最小的前提下使距离最短。然而这种思路存在缺陷：即使当前已知最小费用cost < K，其所对应的最短路径可能不是全局最优解。可能存在另一种情况，花费为cost1（cost < cost1 ≤ K），而其对应的最短路径比之前的更优。
因此，采用优先队列优化的SPFA算法来解决此问题。每当访问某节点时，若当前累计费用不超过K，则将该节点加入队列。同一节点可能多次入队和出队，优先队列确保在费用不超过K的前提下，优先处理距离最小的节点，从而避免上述问题。
实现代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN = 110;
const int MAXM = 10010;
struct Edge {
int to, len, cost;
int next;
} edges[MAXM * 2];
int head[MAXN], edgeCount;
int maxCost, numCities, numEdges;
void initGraph() {
edgeCount = 0;
memset(head, -1, sizeof(head));
}
void addEdge(int from, int to, int length, int cost) {
edges[edgeCount].to = to;
edges[edgeCount].len = length;
edges[edgeCount].cost = cost;
edges[edgeCount].next = head[from];
head[from] = edgeCount++;
}
struct State {
int city, distance, cost;
bool operator>(const State& other) const {
if (distance == other.distance)
return cost > other.cost;
return distance > other.distance;
}
};
int spfa(int start, int end) {
priority_queue<State, vector<State>, greater<State>> pq;
State initial = {start, 0, 0};
pq.push(initial);
while (!pq.empty()) {
State current = pq.top();
pq.pop();
if (current.city == end)
return current.distance;
for (int i = head[current.city]; i != -1; i = edges[i].next) {
State next = {
edges[i].to,
current.distance + edges[i].len,
current.cost + edges[i].cost
};
if (next.cost <= maxCost) {
pq.push(next);
}
}
}
return -1;
}
int main() {
while (scanf("%d", &maxCost) != EOF) {
scanf("%d%d", &numCities, &numEdges);
initGraph();
for (int i = 0; i < numEdges; ++i) {
int from, to, len, cost;
scanf("%d%d%d%d", &from, &to, &len, &cost);
addEdge(from, to, len, cost);
}
int result = spfa(1, numCities);
printf("%d\n", result);
}
return 0;
}
