题目很长，题意简述可为给定一个动态图(边权随已知最短路径周期变化)，求从X到Y的最短路径。我们只需把换乘车等待的时间看作动态的边长度。
按照路径构造有向图，构图后用一般的最短路径算法(Dijkstra,SPFA)即可解决，关键在松弛边时计算动态的边权。对于每条有向 边，需要记录其长度len，所属的线路b，从线路起点到该边的起始端的距离前缀长度pre。在松弛时，已知当前最短路为S，该边前缀pre，该边所属线路 的周期C，边长len。则我们所需等车的最短时间T，如果(A-pre)能整除C，T=A-pre；如果(A-pre)不能整除C，T=((A- pre)/C+1)*C (/为整除)。动态的边权E=len+T，用动态E松弛即可。
/*
* Problem: POI2001 pod
* Author: Guo Jiabao
* Time: 2009.2.3 20:50
* State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN=1001,MAXK=2001,MAXE=8001,INF=0x7FFFFFFF;
struct edge{int t,len,belong,pre;edge *next;};
struct adjl{edge *f,*l;};
struct queue{int Q[MAXN],size,head,tail;};
int N,K,X,Y,G,M,Ec=-1,Ans;
int C[MAXK];
adjl Ad[MAXN];
edge E[MAXE];
queue Q;
bool inq[MAXN];
void Q_ins(int p)
{
inq[p]=true;
Q.size++;
if (++Q.head>=MAXN) Q.head=0;
Q.Q[Q.head]=p;
}
int Q_pop()
{
int rv=Q.Q[Q.tail];
inq[rv]=false;
Q.size--;
if (++Q.tail>=MAXN) Q.tail=0;
return rv;
}
void addedge(int a,int b,int len,int belong,int pre)
{
if (Ad[a].l)
Ad[a].l=Ad[a].l->next=&E[++Ec];
else
Ad[a].f=Ad[a].l=&E[++Ec];
E[Ec].t=b;
E[Ec].len=len;
E[Ec].belong=belong;
E[Ec].pre=pre;
}
void init()
{
int L,i,j,Path[MAXN],Route[MAXN],S;
freopen("pod.in","r",stdin);
freopen("pod.out","w",stdout);
scanf("%d%d%d%d%d%d",&N,&K,&X,&Y,&G,&M);
for (i=1;i<=K;i++)
{
scanf("%d%d",&L,&C[i]);
for (j=1;j<=L;j++)
scanf("%d",&Path[j]);
for (j=1;j<L;j++)
scanf("%d",&Route[j]);
for (S=0,j=1;j<L;j++)
{
addedge(Path[j],Path[j+1],Route[j],i,S);
S+=Route[j];
}
for (S=0,j=L-1;j>=1;j--)
{
addedge(Path[j+1],Path[j],Route[j],i,S);
S+=Route[j];
}
}
Q.head=-1;
}
void spfa()
{
int i,sp[MAXN],u,v,e,pre,c;
for (i=1;i<=N;i++)
sp[i]=INF;
sp[X]=960000+M;
Q_ins(X);
while (Q.size)
{
u=Q_pop();
for (edge *k=Ad[u].f;k;k=k->next)
{
v=k->t;pre=k->pre;c=C[k->belong];
e=(sp[u]-pre)/c*c;
if ((sp[u]-pre)%c)
e+=c;
e+=pre-sp[u]+k->len;
if (sp[u]+e<sp[v])
{
sp[v]=sp[u]+e;
if (!inq[v])
Q_ins(v);
}
}
}
Ans=sp[Y]-960000;
}
void print()
{
int H=G,M;
H+=Ans / 60;
M=Ans % 60;
H%=24;
printf("%d %d",H,M);
}
int main()
{
init();
spfa();
print();
return 0;
}
<h2><span class="mw-headline">旅行</span></h2>
让我们先确定某个城市的交通网络图，图中的点（编号为1..n），表示车站；边(pi,pj) (其中pi≠pj)，表示有一条路线直接连接车站pi和pj(1≤pi, pj≤n)。城市中的公共汽车线路从1到k编号。在线路l上有车站pl,1, pl,2,...,pl,sl,，用rl,1, rl,2,...,rl,sl-1表示对应相邻两车站间的行驶时间。例如rl,1 是从车站pl,1 到pl,2所需的时间，rl,2是从车站pl,2到pl,3所需的时间。同一线路上的车站互不相同(即若i≠j则pl,i≠pl,j)。在线路l上，发车 时间有固定的周期，表示为cl， 其中cl 属于集合{6, 10, 12, 15, 20, 30, 60}；而且在每个整点g:0 (0≤g≤23)，从车站pl,1 必有一辆车出发。于是可知在g:cl,、g:2cl,... 时(g:cl 表示g小时后的cl分钟)，都有车出发。所有的路线均为双向：从车站pl,1到pl,sl ，从车站pl,sl 到 pl,1，且同时以车。在这样的一个城市中，我们打算做一次从车站x到车站y的旅行。你可以假定该旅行是能够完成的，而且所需的时间不超过24小时。旅行 中在任一车站我们都可以换车，上下车的时间不计，但等车的时间要计算在内。我们的目的是尽可能快地完成从车站x到车站y的旅行。
下图是一个有6个车站的交通网，有两条公共汽车线路。线路1：经过车站1、3、4、6；线路2：经过车站2、4、3、5。发车的周期是：c1=15，c2=20。相邻车站间行驶时间己标在图中的边上，以下标1、2表示不同的线路。
<a class="image" title="Image:Pod.gif" href="http://www.ruvtex.cn/wiki/Image:Pod.gif"><img src="http://www.ruvtex.cn/mw/images/0/0f/Pod.gif" alt="Image:Pod.gif" width="383" height="182" /></a>
假定在23:30我们在车站5，目标是到车站6。则必须等10分钟(在23:40)才有一班2路车从车站5出发。接下来有两种旅行方案，其 一：在23:51到达车站3，等3分钟，改乘1路车到达车站6(0:16)。其二：继续乘2路车到车站4(0:8)，再等13分钟(0:21)乘1路车到 车站6(0:31)。因此到达车站6时最早的时间是0:16。
任务：
-
从文件中读入对交通网的描述，交通路线，起始车站x，终点车站y，旅行开始的时间gx和mx(gx表示小时，mx表示分钟)；
-
找出从x到y的最早到达时间；
-
把到车站y的最早时间gy：my写入文件。
输入：
文件的第一行是6个用空格分开的整数：
-
车站总数n（1≤n≤1000）；
-
路线数目k（1≤k≤2000）；
-
起点车站x（1≤x≤n）；
-
终点车站y（1≤y≤n）；
-
旅行开始时刻中的小时gx（0≤gx≤23）；
-
旅行开始时间中的分钟mx（0≤mx≤59）。
车站从1至n编号，路线从1至k编号。接下来的3k行用来描述路线，每条路线的描述占3行：
-
描述路线l的第一行是两个用一空格分开的整数：sl和cl，分别表示路线经过的车站数目和发车周期，其中2≤sl≤n，cl属于集合｛6,10,15,20,30,60｝。
-
描述路线l的第二行有sl个不同的整数，以一个空格分开：pl,1,pl,2,…,pl,sl，表示路线l经过车站的编号( 当1≤i≤sl时，1≤pl,i≤n)。
-
描述路线l的第三行有sl-1个用空格分开的整数：rl,1, rl,2,…, rl,sl-1，表示路线l上相邻两车站间的行驶时间，以分钟作为单位( 当1≤i≤sl-1时，1≤rl,i≤240)。
所有路线的车站数目之和不超过4000（即s1+s2+…+sk≤4000）。
输出：
文件中仅有两个用一空格分开的整数，即最早到达终点的时间：gy和my，（0≤gy≤23，0≤my≤59）。
输入样例：
6 2 5 6 23 30 4 15 1 3 4 6 9 12 10 4 20 5 3 4 2 11 17 11
输出样例：
0 16
上次修改时间 2017-05-22