【分层最短路】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.");

}