最短路 Dijkstra

求一个图中两个点之间最短距离的最快的一种方法，要求路径的花费不能有负的。
时间复杂度：O(ElogE)

模板代码

struct Edge {
    int from, to, dist;
};
struct HeapNode {
    int d, u;
    bool operator  < (const HeapNode & rhs) const {
        return d > rhs.d;
    }
};

struct Dijkstra {
    int n, m;
    vector<Edge> edges;
    vector<int> G[maxn];
    bool done[maxn];
    int d[maxn];
    int p[maxn];

    void init(int n) {
        this -> n = n;
        for (int i = 0; i < n; i++) G[i].clear();
        edges.clear();
    }
    void AddEdge(int from, int to, int dist) {
        edges.push_back((Edge){from, to, dist});
        m = edges.size();
        G[from].push_back(m-1);
    }
    void dijkstra(int s) {
        priority_queue<HeapNode> Q;
        for (int i = 0; i < n; i++) d[i] = INF;
        d[s] = 0;
        memset(done, 0, sizeof(done));
        Q.push((HeapNode){0, s});
        while (!Q.empty()) {
            HeapNode x = Q.top(); Q.pop();
            int u = x.u;
            if (done[u]) continue;
            done[u] = true;
            for (int i = 0; i < (int)G[u].size(); i++) {
                Edge &e = edges[G[u][i]];
                if (d[e.to] > d[u] + e.dist && d[u] + e.dist <= c) {
                    d[e.to] = d[u] + e.dist;
                    if (pp[e.to]) d[e.to] = 0;
                    p[e.to] = G[u][i];
                    Q.push((HeapNode){d[e.to], e.to});
                }
            }
        }

    }
}

ZOJ 3794 Greedy Driver

在n个点m条边的有向图中，一个人有一个车，油箱容量为C。有p个城市可以用加油卡加任意多的油，有q个城市可以卖油，每单位的价格为q_i，在这个人有无数张加油卡的情况下，从1加满油跑到n，只卖一次油，最多可以卖出多少钱的油？

从1跑一次最短路，d[i]表示到i点最少消耗的油量，如果i点是加油站，更新d[i] = 0。left[i] = C – d[i]表示到达第i个点最多剩下多少单位的油，从n跑一次最短路，cost[i]代表从n到每个点的最小花费，剩的油的最大值就是max(p[i] * (left[i] – cost[i]))，i为每个可以卖油的城市。(松弛操作的时候注意油箱的容量限制)

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

const int maxn = 1500;
const long long INF = 0x3f3f3f3f;
struct Edge {
    int from, to, dist;
};
struct HeapNode {
    int d, u;
    bool operator  < (const HeapNode & rhs) const {
        return d > rhs.d;
    }
};

int pp[maxn], c;
struct Dijkstra {
    int n, m;
    vector<Edge> edges;
    vector<int> G[maxn];
    bool done[maxn];
    int d[maxn];
    int p[maxn];

    void init(int n) {
        this -> n = n;
        for (int i = 0; i < n; i++) G[i].clear();
        edges.clear();
    }
    void AddEdge(int from, int to, int dist) {
        edges.push_back((Edge){from, to, dist});
        m = edges.size();
        G[from].push_back(m-1);
    }
    void dijkstra(int s) {
        priority_queue<HeapNode> Q;
        for (int i = 0; i < n; i++) d[i] = INF;
        d[s] = 0;
        memset(done, 0, sizeof(done));
        Q.push((HeapNode){0, s});
        while (!Q.empty()) {
            HeapNode x = Q.top(); Q.pop();
            int u = x.u;
            if (done[u]) continue;
            done[u] = true;
            for (int i = 0; i < (int)G[u].size(); i++) {
                Edge &e = edges[G[u][i]];
                if (d[e.to] > d[u] + e.dist && d[u] + e.dist <= c) {
                    d[e.to] = d[u] + e.dist;
                    if (pp[e.to]) d[e.to] = 0;
                    p[e.to] = G[u][i];
                    Q.push((HeapNode){d[e.to], e.to});
                }
            }
        }

    }
}G, H;

int q[maxn], left[maxn], city[maxn];

int main() {
    //freopen("in.txt", "r", stdin);
    int n, m, x, y;
    while (scanf("%d%d%d", &n, &m, &c) != EOF) {
        H.init(n+1);
        G.init(n+1);
        for (int i = 0; i < m; i++) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            H.AddEdge(u, v, w);
            G.AddEdge(v, u, w);
        }
        memset(pp, 0, sizeof(pp));
        memset(q, 0, sizeof(q));
        scanf("%d", &x);
        for (int i = 0; i < x; i++) {
            scanf("%d", &y);
            pp[y] = 1;
        }
        scanf("%d", &x);
        for (int i = 0; i < x; i++) {
            scanf("%d%d", &city[i], &q[i]);

        }
        H.dijkstra(1);
        if (H.d[n] == INF) {
            puts("-1");
            continue;
        }
        G.dijkstra(n);
        for (int i = 0; i < x; i++) left[city[i]] = c - H.d[city[i]];

        int ans = 0;
        for (int i = 0; i < x; i++)
            if(q[i] > 0 && left[city[i]] > 0 && left[city[i]] - G.d[city[i]] > 0)
                ans = max(ans, (left[city[i]] - G.d[city[i]]) * q[i]);
        printf("%d\n", ans);
    }
    return 0;
}