【分层最短路】Joyride

http://codeforces.com/gym/101873
C

多开一维状态记录时间，d[i][t] = 经过时间t走到节点i的最小花费
每一个状态分别向“原地等待”与“前往下一个节点”转移

代码：

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
const int MAX_V = 1005;
const int MAX_E = 2005;
ll p[MAX_V], t[MAX_V];
int N, M, T, pick;
struct Dijkstra {
    struct Edge {
        int to, next;
        ll cost;
    } es[MAX_E];
    struct Node {
        int u;
        ll d, k;
        Node(int u, ll d, ll k) : u(u), d(d), k(k) {}
        bool operator< (const Node& n) const {
            return d > n.d;
        }
    };
    int head[MAX_V];
    int V, E;
    ll d[MAX_V][1005];
    bool vis[MAX_V][1005];
    void init(int V) {
        this->V = V;
        this->E = 0;
        memset(head, -1, sizeof head);
    }
    void addEdge(int u, int v, ll w) {
        es[E].to = v;
        es[E].cost = w;
        es[E].next = head[u];
        head[u] = E++;
    }
    void dijkstra(int s) {
        priority_queue <Node> Q;
        memset(d, 0x3f, sizeof d);
        memset(vis, 0, sizeof(vis));
        d[s][t[1]] = p[1];
        Q.push(Node(s, p[1], t[1]));
        while (!Q.empty()) {
            int u = Q.top().u;
            ll k = Q.top().k;
            Q.pop();
            if (vis[u][k])
                continue;
            vis[u][k] = true;
            if (k + t[u] <= pick && d[u][k + t[u]] > d[u][k] + p[u]) {
                d[u][k + t[u]] = d[u][k] + p[u];
                Q.push(Node(u, d[u][k + t[u]], k + t[u]));
            }
            for (int i = head[u]; i != -1; i = es[i].next) {
                int v = es[i].to;
                ll w = es[i].cost;
                if (k + w + t[v] <= pick && d[v][k + w + t[v]] > d[u][k] + p[v]) {
                    d[v][k + w + t[v]] = d[u][k] + p[v];
                    Q.push(Node(v, d[v][k + w + t[v]], k + w + t[v]));
                }
            }
        }
    }
} dijk;
int main() {
    scanf("%d%d%d%d", &pick, &N, &M, &T);
    dijk.init(N);
    while (M--) {
        int a, b;
        scanf("%d%d", &a, &b);
        dijk.addEdge(a, b, T);
        dijk.addEdge(b, a, T);
    }
    for (int i = 1; i <= N; i++) {
        scanf("%lld%lld", &t[i], &p[i]);
    }
    dijk.dijkstra(1);
    if (dijk.vis[1][pick])
        printf("%lld\n", dijk.d[1][pick]);
    else
        puts("It is a trap.");
}