AcWing：176. 装满的油箱（bfs + dijiskla思想）

#include 
#include 
#include 
#include 
#include using namespace std;

const int maxn = 1e4+7;

struct node {
    int u, f, w;
    friend bool operator //优先队列重载，权值小的排前面
        return a.w > b.w;
    }
};

vectorint, int> > g[maxn];

int n, m;
int wn[maxn];
int dp[maxn][105];
int vis[maxn][105];
int c, s, e;

bool check1(int u, int f) { //判断是否能够在当前站点加一升油
    if(f + 1 1] && dp[u][f + 1] > dp[u][f] + wn[u]) {   //如果能加一升油，并且加这升油一定比原来的那个好（原来的那个可能是初始化的INF，也可能是已经经过的这个地方时更新的值）
        return true;
    }
    return false;
}

bool check2(int f, int v, int p, int w) {   //判断下一个站点是否能走
    if(f >= p && !vis[v][f - p] && dp[v][f - p] > w) {  //如果当前油要大于需要花费的油，并且原来的费用比现在的要高（同理，可能是INF，也可能是更新过的值）
        return true;
    }
    return false;
}

int bfs() {
    priority_queue q;
    memset(vis, 0, sizeof vis);
    memset(dp, 0x3f3f3f3f, sizeof dp);
    dp[s][0] = 0;
    q.push((node){s, 0, 0});
    while(!q.empty()) {
        node now = q.top();
        q.pop();
        int u = now.u;
        int f = now.f;
        int w = now.w;
        vis[u][f] = 1;
        if(u == e) {
            return w;
        }
        if(check1(u, f)) {      //先加一升油试一下
            dp[u][f + 1] = dp[u][f] + wn[u];
            q.push((node){u, f + 1, dp[u][f + 1]});
        }
        int len = g[u].size();
        for(int i = 0; i ) {
            int v = g[u][i].first;
            int p = g[u][i].second;
            if(check2(f, v, p, w)) {
                dp[v][f - p] = w;
                q.push((node){v, f - p, w});
            }
        }
    }
    return -1;  //无解
}

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 0; i ) {
        scanf("%d", &wn[i]);
    }
    for(int i = 1; i ) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        g[u].push_back(make_pair(v, w));
        g[v].push_back(make_pair(u, w));
    }
    int q;
    scanf("%d", &q);
    while(q--) {
        scanf("%d %d %d", &c, &s, &e);
        int ans = bfs();
        if(ans == -1) {
            printf("impossible\n");
        } else {
            printf("%d\n", ans);
        }
    }
    return 0;
}