题解：P13432 [GCJ 2009 #1A] Crossing the Road

· · 题解

非常考验编码能力和阅读理解的最短路问题。

Problem

在一个 N 行 M 列的网格城市中，行人要从西南角的东北角走到东北角的西南角。目标是找到最短到达终点的时间。

规则如下：

Solution

注意到在同一个街区的四个角落，其包含的实际意义是不一样的（如在某一街区的左下角时，无法直接通过右上角的那个路口），直接处理要写很多判断。于是我们可以将一个完整的街区分成四块，以便于分类处理它们。

使用 Dijkstra 求最短路。每个状态包含当前时间 t 和所在位置 (xx, yy)，用优先队列按时间 t 从小到大排序，保证每次处理当前最短时间的状态。

动态边权的计算：

  1. 沿边缘移动：固定 2 分钟，无等待。
  2. 横穿马路：原本就要的 1 分钟，通过周期（S+W）计算当前时间在周期中的位置，从而得到等待时间（wt 函数）。

为什么不用宽搜：直接宽搜无法保证正确性，因为边权不同（可能对同一个位置上时间较大的状态更新，第一个到达终点的状态可能不是最快的）。

Code

#include<bits/stdc++.h> 
using namespace std;
const int N=50;
const int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
struct Node { int s,w,t; };
struct State 
{
    int t,xx,yy; 
    bool operator < (const State & tp) const
    {
        return t>tp.t;
    }
};

int C;

int n,m;
Node a[N][N];
int tme[N][N];
int dis(int x,int y,int dir)
{
    if(dir==0 or dir==1)
        return ((dir+x)%2==0)?1:2;
    if(dir==2 or dir==3)
        return ((dir+y)%2==0)?1:2;
}

int wt(int x,int y,int dir,int curtime,int S,int W,int T)
{
    int cycle=S+W;
    curtime=(curtime-T+cycle)%cycle;

    if(curtime<S)// 南北向绿灯时段
    { 

        if(dir==1 or dir==0)
            return 0;
        else 
            return S-curtime;
    }
    else // 东西向绿灯时段
    { 
        if(dir==2 or dir==3)
            return 0;
        else 
            return cycle-curtime;
    }
}
void solve(int CC)
{
    memset(tme,0x3f,sizeof(tme));
    cin>>n>>m;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j].s>>a[i][j].w>>a[i][j].t;
            a[i][j].t%=(a[i][j].s+a[i][j].w);
        }
    }

    priority_queue<State>q;

    q.push({0,n*2,1});
    tme[n*2][1]=0;

    while(!q.empty())
    {
        State cur=q.top();
        q.pop();
        if(cur.t>tme[cur.xx][cur.yy]) continue;//删去非最优的状态
        if(cur.xx==1 and cur.yy==m*2)
        {
            cout<<"Case #"<<CC<<": "<<cur.t<<"\n";
            return ;
        }

        for(int i=0;i<4;i++)
        {
            int nx=cur.xx+dx[i],ny=cur.yy+dy[i];

            if(nx<1 or nx>n*2 or ny<1 or ny>m*2)
                continue;
            int stx=(cur.xx-1)/2+1,sty=(cur.yy-1)/2+1;
            int nt=cur.t+dis(cur.xx,cur.yy,i);

            if(dis(cur.xx,cur.yy,i)==1)// 如果是横穿马路，加上等待时间
                nt+=wt(cur.xx,cur.yy,i,cur.t,a[stx][sty].s,a[stx][sty].w,a[stx][sty].t);

            if(nt>=tme[nx][ny])continue;

            tme[nx][ny]=nt;
            q.push({nt,nx,ny});
        }
    }
}
int main()
{
    cin>>C;
    for(int i=1;i<=C;i++)
        solve(i);
    return 0; 
}

Tip

dis 函数的朴素写法

int dis(int x,int y,int dir)
{
    if(dir==0)//north
        if(x%2==0) return 1; else return 2;
    else if(dir==1)//south
        if(x%2==1) return 1; else return 2;
    else if(dir==2)//west
        if(y%2==0) return 1; else return 2;
    else if(dir==3)//east
        if(y%2==1) return 1; else return 2;
    return -1;
}

在草稿纸上画一个把街区分成四块的图更有利于理解哦~