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;
}