题目描述
有N个城市(编号0、1…N-1)和M条道路,构成一张无向图。
在每个城市里边都有一个加油站,不同的加油站的单位油价不一样。
现在你需要回答不超过100个问题,在每个问题中,请计算出一架油箱容量为C的车子,从起点城市S开到终点城市E至少要花多少油钱?
注意: 假定车子初始时油箱是空的。
样例
输入样例:
5 5
10 10 20 12 13
0 1 9
0 2 8
1 2 1
1 3 11
2 3 7
2
10 0 3
20 1 4
输出样例:
170
impossible
算法1
(bfs)
根据题意:
当前点可以用pair
来记录,可以往两个方向扩展
1.<Ver, c> ---> <Ver, c + 1>
2.<Ver, c> ----><Ver, next> 如果 c > 边权。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 1010, C = 110, M = 20010;
int n, m;
int h[N], e[M], w[M], ne[M], idx;
int price[N];
int dist[N][C];
bool st[N][C];
struct Ver{
int d, u, c;//d表示当前总共消耗的油费, u表示当前节点编号, c表示当前油箱剩余容量
bool operator < (const Ver &W) const{
return d > W.d;
}
};
void add (int a, int b, int c){
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
int dijkstra(int start, int end, int cap){
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof st);
priority_queue<Ver> heap;
heap.push({0, start, 0});
dist[start][0] = 0;
while (heap.size()){
auto t = heap.top(); heap.pop();
if (t.u == end) return t.d;
if (st[t.u][t.c]) continue;
st[t.u][t.c] = true;
if (t.c < cap){
if (dist[t.u][t.c + 1] > t.d + price[t.u]){
dist[t.u][t.c + 1] = t.d + price[t.u];
heap.push({dist[t.u][t.c + 1], t.u, t.c + 1});
}
}
for (int i = h[t.u]; ~i; i = ne[i]){
int j = e[i];
if (t.c >= w[i]){
if (dist[j][t.c - w[i]] > t.d){//如果可以扩展,那么扩展到下一个节点。
dist[j][t.c - w[i]] = t.d;
heap.push({dist[j][t.c - w[i]], j, t.c - w[i]});
}
}
}
}
return -1;
}
int main(){
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
for (int i = 0; i < n; i ++) scanf("%d", &price[i]);
for (int i = 0; i < m; i ++){
int a, b , c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c), add(b, a, c);
}
int query;
scanf("%d", &query);
while (query --){
int a, b, c;
scanf("%d%d%d", &c, &a, &b);//注意询问的是 C, S, E。 油箱容量, 开始点, 结束点
int t = dijkstra(a, b, c);
if (t == -1) puts("impossible");
else printf("%d\n", t);
}
return 0;
}