二维(城市,剩下油)状态的bfs
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 1010, M = 20010, H = 110;
int oil_price[N];
int e[M], ne[M], w[M], h[N], idx;
int d[N][H], ans;//d[i][j],表示到达城市i,剩下油为j的最小花费
int n, m, question, C, s, en;
struct P{//结构体
int city, fuel, cost;//分别表示当前城市,油,花费
};
auto cmp = [](const P& A, const P& B) {return A.cost > B.cost;};
priority_queue<P, vector<P>, decltype(cmp)> pq(cmp);//按照花费排序的结构体
//添加一条由a到b的边, 边权为k2
void add(int a, int b, int k){
w[idx] = k;
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void init(){//初始化
memset(d, -1, sizeof d);
ans = 0;
while(!pq.empty()) pq.pop();
}
int main(){
memset(h, -1, sizeof h);
cin >> n >> m;
for(int i = 0; i < n; i++) cin >> oil_price[i];
for(int i = 1; i <= m; i++){
int a, b, k;
cin >> a >> b >> k;
add(a,b,k);
add(b,a,k);
}
cin >> question;
while(question--){
init();
cin >> C >> s >> en;
pq.push({s,0,0});
while(pq.size()){
auto now = pq.top(); pq.pop();
int ci = now.city, f = now.fuel, co = now.cost;
d[ci][f] = co;
if(ci == en)//一旦遇到终点城市就输出,不然TLE
{
cout << co << endl;
break;
}
if(f < C) pq.push({ci, f + 1, co + oil_price[ci]});
for(int i = h[ci]; ~i; i = ne[i]){
if(f >= w[i] && d[e[i]][f-w[i]] == -1)
pq.push({e[i], f - w[i], co});
}
}
if(d[en][0] == -1) cout << "impossible\n";
}
return 0;
}