NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2005高中組決賽
 NPSC 2005 高中組 決賽 F.捷運漫遊

作者 主題: NPSC 2005 高中組 決賽 F.捷運漫遊  (閱讀 1880 次)

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 242
    • 檢視個人資料
NPSC 2005 高中組 決賽 F.捷運漫遊
« 於: 十二月 08, 2009, 02:30:22 pm »

NPSC 2005 高中組 決賽 F.捷運漫遊

說明:給你 N 個車站之間的班車時間間隔以及所花的時間,你從某個時間起由一個站出發,到某個時間為止到另一個站與朋友會合,問你該如何轉乘,才能把大部分的時間都花在坐車上面,也就是要使在月台等候的時間最少。(包括在月台等待下一班車的時間以及等朋友會合的時間)

解法:使用 DFS 找出所有可能,並記錄到目前為止最少的等待時間,如果其中一種走法的等待時間已經等於或超過最少的等候時間,則該走法就放棄不再走下去。

參考程式:(By sagit)

代碼: [選擇]
// NPSC 2005 決賽 - 題目 F - 捷運漫遊 //
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#include <cstdlib>
#define MAX 101

using namespace std;

struct Station {
    int Target;   // 目的站
    int Interval; // 時間間隔
    int Time;     // 所花時間
};

vector< deque<Station> > Info; // 記錄各站班車資訊

struct Trip {
    int Station;  // 所在的站
    int Now;      // 到站時間
    int Wait;     // 已等待時間
};

deque<Trip> Stack; // DFS 用堆疊

int main()
{
    ifstream fin("pf.in");
    ofstream fout("pf.out");
    int n, m, from, to, begin, end, min, a, i;
    char c;
    Station s;
    Trip t, t2;
    deque<Station>::iterator it;

    while (1)
    {
        fin >> n >> m;
        if ( n==0 || fin.fail() ) break;
        // 歸零
        Info.clear();
        Info.resize(n+1);
        // 輸入各班車資訊
        for (i=0; i<m; i++)
        {
            fin >> a >> s.Target >> s.Interval >> s.Time;
            Info[a].push_back(s);
        }
        // 輸入起點、終點、開始時間、結束時間
        fin >> from >> to;
        fin >> a >> c >> i;
        begin=a*60+i;
        fin >> a >> c >> i;
        end=a*60+i;
        // DFS 起啟動作
        min=end+1;
        Stack.clear();
        t.Station=from;
        t.Wait=0;
        t.Now=begin;
        Stack.push_back(t);
        while (1)
        {
            if ( Stack.empty() ) break;
            t=Stack.back();
            Stack.pop_back();
            if ( t.Now>end ) continue; // 超過時間
            if ( t.Wait>=min ) continue; // 等於或超過最小等待時間
            if ( t.Station==to ) // 到達終點
            {
                a=t.Wait+end-t.Now; // 加上等待朋友的時間
                if ( a<min ) min=a;
                if ( min==0 ) break;
            }
            for (it=Info[t.Station].begin(); it!=Info[t.Station].end(); ++it)
            {
                t2.Station=it->Target;
                a=t.Now%it->Interval;
                if ( a!=0 ) a=it->Interval-a; // 等車時間
                t2.Wait=t.Wait+a;
                t2.Now=t.Now+a+it->Time;
                Stack.push_back(t2);
            }
        }
        if ( min>end ) fout << "No way" << endl;
        else fout << min << endl;
    }

//    system("PAUSE");
    return 0;
}
記錄

suhorng

  • 初級會員
  • **
  • 文章數: 26
    • 檢視個人資料
回覆: NPSC 2005 高中組 決賽 F.捷運漫遊
« 回覆 #1 於: 三月 23, 2010, 11:32:16 am »

也可以當成 N * T 個點的最短路(或DP!?)來寫

想法就是,把「我在時間 t 到達(位於)節點 v」當做一個新的節點

而我們要記的就是到達該節點的最少等待時間
記錄

liouzhou_101

  • 初級會員
  • **
  • 文章數: 44
    • 檢視個人資料
回覆: NPSC 2005 高中組 決賽 F.捷運漫遊
« 回覆 #2 於: 七月 18, 2010, 11:58:37 am »

其实还有DP的算法啦!
//和suhorng想法的差不多,我讲详细点...
令start为起始时间,final为达到时间,ps为出发地点,pt为目标地点。
令ans[i,j]表示时间为i时到达地点j所须最少等待时间,那么有
ans[i+1,j]=min{ans[i+1,j],a[i,j]+1}

ans[i+car[j].time[k],car[j].next[k]]=min{ans[i+car[j].time[k],car[j].next[k]],ans[i,j]}
(当i%car[j].pre[k]==0时)
其中 car[]表示从某个地点出发的车的信息,并且类型为
struct car_type{
int num                   //表示车的总量
     ,time[1440]        //表示行驶所需时间
     ,next[1440]        //表示车的去向
     ,pre[next];         //表示每隔多少时间发一次车
}

这样可以一步步推出所需答案ans[final,pt]

以上DP方程的初始化为 ans[i,j]=maxint;  //设为一个足够大的数
这样若答案ans[final,pt]==maxint,就说明无解,输出“No way”。

//其实我是用pascal的,但为了大家看得懂,在以上解法叙述时用了C++的习惯。
//但我的程序还是贴pascal的吧...

这样
时间复杂度为 O((final-start)*n*m)=O(time*n*m)
空间复杂度为 O(1440*n+n*m)=O(n*m)

实际运行速度超快:4xx ms

以下贴程序作参考://程序十分精简的!!
代碼: [選擇]
var n,m,ps,pt,start,final : longint;
    ans : array[0..1440,1..100] of longint;
    car : array[1..100] of record
            num : longint;
            next,pre,time : array[1..1000] of longint;
          end;
function min(a,b:longint):longint;
  begin
    if a<=b then min:=a
      else min:=b;
  end;
procedure init;
  var i,j,x,y,p,t : longint;
      s : string;
  function get(s:string):longint;
    begin
      get:=((ord(s[1])-48)*10+ord(s[2])-48)*60+(ord(s[4])-48)*10+ord(s[5])-48;
    end;
  begin
    for i:=1 to n do
      car[i].num:=0;                                                  //初始化
    for i:=1 to m do begin
      readln(x,y,p,t);
      with car[x] do begin
        num:=num+1;
        next[num]:=y;
        pre[num]:=p;
        time[num]:=t;
      end;
    end;
    readln(ps,pt);
    readln(s);
    start:=get(s);
    readln(s);
    final:=get(s);
    for i:=start to final do
      for j:=1 to n do
        ans[i,j]:=maxint;                                   //初始化,其中maxint在pacal中默认为32767
    ans[start,ps]:=0;
  end;
procedure work;
  var i,j,k : longint;
  begin
    for i:=start to final-1 do begin
      for j:=1 to n do
        ans[i+1,j]:=min(ans[i+1,j],ans[i,j]+1);
      for j:=1 to n do
        with car[j] do
          for k:=1 to num do
            if i mod pre[k]=0 then
              ans[i+time[k],next[k]]:=min(ans[i+time[k],next[k]],ans[i,j]);    //重要的DP
    end;
    if ans[final,pt]=maxint then writeln('No way')
      else writeln(ans[final,pt]);
  end;
begin
  while true do begin
    readln(n,m);
    if n=0 then exit;
    init;                                                             //输入以及预处理
    work;                                                           //计算答案
  end;
end.
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2005高中組決賽
 NPSC 2005 高中組 決賽 F.捷運漫遊