POI 2001 Travel 旅行

題目很長,題意簡述可爲給定一個動態圖(邊權隨已知最短路徑週期變化),求從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

相關日誌