本文正體字版由OpenCC轉換
題目很長，題意簡述可爲給定一個動態圖(邊權隨已知最短路徑週期變化)，求從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