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

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

Problem

在一个

N

行

M

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

规则如下：

横穿马路需 $1$ 分钟，若红灯需要等待。
沿街区边缘走（从一个角走到相邻角）需 $2$ 分钟，无需等待。
每个路口的信号灯按固定周期切换：先南北向绿灯（持续 $S$ 分钟），再东西向绿灯（持续 $W$ 分钟），循环往复，且从 $T$ 时刻开始以南北绿灯为起点。

Solution

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

使用 Dijkstra 求最短路。每个状态包含当前时间

t

和所在位置

(xx, yy)

，用优先队列按时间

t

从小到大排序，保证每次处理当前最短时间的状态。

动态边权的计算：

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

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

Code

CPP

#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 函数的朴素写法

CPP

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;
}

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

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

文章操作

Problem

Solution

Code

Tip

相关推荐

评论

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