【COGS 254】【POI 2001】交通网络图

http://www.cogs.top/cogs/problem/problem.php?pid=254

dist[i]表示能最早到达i点的时间。这样就可以用最短路模型来转移了。

#include<queue>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 1003;

const int K = 2003;

int in() {

	int k = 0, fh = 1; char c = getchar();

	for(; c < '0' || c > '9'; c = getchar())

		if (c == '-') fh = -1;

	for(; c >= '0' && c <= '9'; c = getchar())

		k = (k << 3) + (k << 1) + c - '0';

	return k * fh;

}

struct que {

	int id, dist;

	que(int _id = 0, int _dist = 0) : id(_id), dist(_dist) {}

	bool operator < (const que &A) const {

		return dist > A.dist;

	}

};

struct node {int nxt, to, w, c, sum;} E[10003];

int gx, mx, x, y, n, k, cnt = 0, point[N];

int p[N], r[N], dist[N], pre[N], note[N];

bool vis[N];

void ins(int u, int v, int w, int c, int sum) {

	E[++cnt] = (node) {point[u], v, w, c, sum}; point[u] = cnt;

}

int cal(int a, int b, int c) {

	a = a % c; b = b % c;

	if (a >= b) return a - b;

	else return a - b + c;

}

void dijkstra() {

	priority_queue <que> q;

	q.push(que(x, dist[x]));

	que u; int t;

	while (!q.empty()) {

		u = q.top(); q.pop();

		if (vis[u.id]) continue;

		vis[u.id] = true;

		for(int i = point[u.id]; i; i = E[i].nxt)

			if ((t = (dist[u.id] + cal(E[i].sum, dist[u.id], E[i].c) + E[i].w)) < dist[E[i].to])

				dist[E[i].to] = t, q.push(que(E[i].to, t));

	}

}

int main() {

	freopen("pod.in", "r", stdin);

	freopen("pod.out", "w", stdout);

	n = in(); k = in(); x = in(); y = in(); gx = in(); mx = in();

	int s, c, ret;

	for(int i = 1; i <= k; ++i) {

		s = in(); c = in();

		for(int i = 1; i <= s; ++i)

			p[i] = in();

		for(int i = 1; i < s; ++i)

			r[i] = in();

		ret = 0;

		for(int i = 1; i < s; ++i) {

			ins(p[i], p[i + 1], r[i], c, ret);

			ret += r[i];

		}

		ret = 0;

		for(int i = s - 1; i >= 1; --i) {

			ins(p[i + 1], p[i], r[i], c, ret);

			ret += r[i];

		}

	}

	memset(dist, 127, sizeof(int) * (n + 1));

	dist[x] = mx;

	dijkstra();

	ret = dist[y];

	printf("%d %d\n", (gx + ret / 60) % 24, ret % 60);

	return 0;

}