首页 > ACM题库 > HDU-杭电 > HDU 3462-Date[解题报告]HOJ
2014
03-30

HDU 3462-Date[解题报告]HOJ

Date

问题描述 :

Is it just another problem about year, month and day? No, today we have a more romantic meaning � dating with a girl.
iSea now has a date to be anxious to rush, unfortunately, the city’s way is always so complicated, so time goes unconsciously and fast. In order to more quickly rushed to rendezvous, iSea has already drawn a topographic map of this city, he find that the city is composed of a number of equal squares, between the squares, there are some traffic lights controlling the traffic, a basic map example:
Code Lock
Each time, iSea must proceed from the starting point of the upper left corner to reach the lower right corner. The squares’ size is fixed, with a length of two meters and a width of one meter. iSea usually only go across the intersection under the green light, the time he costs is one minute, for safety’s sake, in the whole one minute the green light should be lighten, we also know, iSea’s speed along the grid is a constant, one meter per minute.
iSea’s map gives some more specific information about the city, the number of vertical grid N, the number of horizontal grid M, and the time the traffic lights change alternating. In order to simplify the problem, we assume that one day start at 0 hour, traffic lights first allow passengers traverse the intersection from left and right, but block up and down in the intersection, after a time Ti, the traffic lights block left and right to allow access up and down, the time is also the Ti, so the cycle goes.
After simple calculation, iSea finds he may be late for this date, in order to reach the destination in time, he decides to make one exception, in an emergency he would pass through a intersection even if a red light was lighten, but not to loss of too many RP, he asks himself go across the red light at most once, then, can you help him, calculate when he could arrive in rendezvous at the earliest?

输入:

There are several test cases in the input.

Each test case begin with two integers N, M (1 < N, M ≤ 30), indicating the number of the vertical grid and the horizontal grid.
Then N-1 lines follow, each line contains M-1 numbers Ti (0 < Ti ≤ 10), their meaning is in the description.
The last line is the start time of iSea, in the form of HH:MM.

The input terminates by end of file marker.

输出:

There are several test cases in the input.

Each test case begin with two integers N, M (1 < N, M ≤ 30), indicating the number of the vertical grid and the horizontal grid.
Then N-1 lines follow, each line contains M-1 numbers Ti (0 < Ti ≤ 10), their meaning is in the description.
The last line is the start time of iSea, in the form of HH:MM.

The input terminates by end of file marker.

样例输入:

2 2
3
12:03
2 3
2 2
12:00

样例输出:

12:05
12:05

#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

#define inf 1000000000
struct edge
{
	int to,cost,next;
	int T, mod;
}e[32000];
struct node
{
	int x,y,z;
	node(int _x=0, int _y=0, int _z):x(_x),y(_y),z(_z){}
	bool operator<(const node& a)const
	{
		return y>a.y;
	}
};
priority_queue<node> que;
bool visit[4000];
int dis[4000][2];
int pre[4000];

int next[8000];
int n,m,num;
int a[40][40];

void addedge(int from, int to, int cost, int T, int mod)
{
	e[num].to=to;e[num].cost=cost;
	e[num].T=T;e[num].mod=mod;
	e[num].next=pre[from];
	pre[from]=num;
	num++;
}


void make_map()
{
	num=1;
	memset(pre, 0, sizeof(pre));
	for (int i=0; i<n; i++)
	for (int j=0; j<m; j++)
	{
		addedge(4*i*m+4*j, 4*i*m+4*j+1, 1, a[i][j], 1);addedge(4*i*m+4*j+1, 4*i*m+4*j, 1, a[i][j], 1);
		addedge(4*i*m+4*j, 4*i*m+4*j+2, 1, a[i][j], 0);addedge(4*i*m+4*j+2, 4*i*m+4*j, 1, a[i][j], 0);
		addedge(4*i*m+4*j+3, 4*i*m+4*j+1, 1, a[i][j],0);addedge(4*i*m+4*j+1, 4*i*m+4*j+3, 1, a[i][j], 0);
		addedge(4*i*m+4*j+3, 4*i*m+4*j+2, 1, a[i][j],1);addedge(4*i*m+4*j+2, 4*i*m+4*j+3, 1, a[i][j], 1);
		if (j!=m-1)
		{
			addedge(4*i*m+4*j+1,4*i*m+4*(j+1),2,0,0);addedge(4*i*m+4*(j+1),4*i*m+4*j+1,2,0,0);
			addedge(4*i*m+4*j+3,4*i*m+4*(j+1)+2,2,0,0);addedge(4*i*m+4*(j+1)+2,4*i*m+4*j+3,2,0,0);
		}
		if (i!=n-1)
		{
			addedge(4*i*m+4*j+2,4*(i+1)*m+4*j,1,0,0);addedge(4*(i+1)*m+4*j,4*i*m+4*j+2,1,0,0);
			addedge(4*i*m+4*j+3,4*(i+1)*m+4*j+1,1,0,0);addedge(4*(i+1)*m+4*j+1,4*i*m+4*j+3,1,0,0);
		}
	}
}

void get_in(int to,int cost,int id)
{
	if (dis[to][id]<=cost||dis[to][0]<=cost) return;
	dis[to][id]=cost;
	que.push(node(to,cost,id));
}

int dfs(int x,int tt)
{
	while(!que.empty()) que.pop();
	for (int i=0;i<4*n*m;i++)
	{
		visit[i]=0;
		dis[i][0]=dis[i][1]=inf;
	}
	que.push(node(x,tt,0));
	while(!que.empty())
	{
		node out=que.top();
		que.pop();
		int x=out.x,y=out.y,z=out.z;
		if (visit[x]) continue;
		if (z==0)
		visit[x]=1;
		if (x==4*n*m-1) break;
		for (int i=pre[x]; i!=0; i=e[i].next)
		if (!visit[e[i].to])
		{
			int ty;
			if (e[i].T==0)
			{
				ty=y+e[i].cost;
				get_in(e[i].to,ty,z);
			}
			else
			{
				int tmp=(y+e[i].T-1)/e[i].T;
				if (y%e[i].T==0) tmp++;
				if (tmp%2==e[i].mod)
				{
					ty=y+1;
					get_in(e[i].to,ty,z);
				}
				else
				{
					if (z==0)
					{
						ty=y+1;
						get_in(e[i].to,ty,1);
					}
					ty=y+e[i].T-y%e[i].T+1;
					get_in(e[i].to,ty,z);
				}
			}
		}
	}
	return min(dis[4*n*m-1][0],dis[4*n*m-1][1]);
}

int main()
{
	while (scanf("%d%d",&n,&m)!=EOF)
	{
		n--;m--;
		for (int i=0; i<n; i++)
		for (int j=0; j<m; j++)
			scanf("%d",&a[i][j]);
		make_map();
		
		char tt[50];
		int ta,tb;
		scanf("%s",tt);
		for (int i=0;tt[i];i++)
		if (tt[i]==':') tt[i]=' ';
		sscanf(tt,"%d %d",&ta,&tb);
		ta=ta*60+tb;
		
		int ans=dfs(0,ta);
		ta=ans/60;
		tb=ans%60;
		printf("%02d:%02d\n",ta,tb);
	}
	return 0;
}

  1. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的