首页 > ACM题库 > HDU-杭电 > HDU 2903-Road-最短路径-[解题报告]HOJ
2014
02-21

HDU 2903-Road-最短路径-[解题报告]HOJ

Road

问题描述 :

In the Green Heart of Holland the villages are small and the roads narrow. Some roads are only one car wide, so if two cars travelling in the opposite direction meet on such a road, they have a problem. In the Green Heart of Holland there usually is a canal at each side of the road, which makes it is impossible for a car to leave the road to let another car pass. To solve this problem,the roads here and there are made a bit wider, so one car can get aside, and one or more cars from the other side may pass. This works ne, as long as the trafic density is low. If, within a short period of time, a lot of cars from both sides try to pass the road, the tra c will get stuck. Given the number of cars entering at both sides (and the location of the passing places) there must be an optimal schedule, to have them all pass the road as soon as possible. Finding such a schedule may be quite hard, so we will not ask you to do so. We ask you to solve a more simple problem.

Given is a road (running East-West), with its passing points, a number of eastbound cars and a number of westbound cars. (An eastbound car enters the road at the West side). Furthermore a schedule is given, that is, for every pair (e,w), where e is an eastbound car and w is a westbound car, the place where they pass each other is given. If the cars enter the road with long delays, such a schedule may take an arbitrary long time. We assume, however, that all cars are ready to enter the road, and eager to leave the road as soon as possible. We measure the time between the moment the rst car enters the road, and the moment the last car leaves the road, and we want that interval to be as short as possible. All cars either stand still, or are driving with a constant speed of 45 km/h. Starting and stopping does not take any time. Two cars driving in the same direction always keep a distance of at least 25 meter. The distance between two different passing places is at least 30 meter. The length of the cars may be ignored.

输入:

The first line of input consists of the integer number n, the number of test cases;
Then, for each test case:
A line containing the length l (0 < l <=30000) of the road in meters, and the number p(0 < p) of passing places;

A line containing p positive integers, the distance in meters from each passing place to the west end of the road. These numbers are sorted in increasing order;

A line containing two positive integers e and w, (0 < e,w <= 1000) the number of eastbound and westbound cars respectively;

e lines, containing w numbers each, indicating the passing points of each pair of cars.The number z on position x (1 <=x<= w) of line y (1 <=y <= e) indicates that the eastbound car y passes the westbound car x at passing point z (0 <=z <= p + 1).Westbound car x enters the road before westbound car x + 1, and eastbound car y enters the road before eastbound car y + 1. The value z = 0 indicates crossing at the west end, so car y enters the road after x has left the road. The value z = p+1, in the same way, indicates crossing at the east side.

All numbers on a line are each separated by one or more spaces.

输出:

The first line of input consists of the integer number n, the number of test cases;
Then, for each test case:
A line containing the length l (0 < l <=30000) of the road in meters, and the number p(0 < p) of passing places;

A line containing p positive integers, the distance in meters from each passing place to the west end of the road. These numbers are sorted in increasing order;

A line containing two positive integers e and w, (0 < e,w <= 1000) the number of eastbound and westbound cars respectively;

e lines, containing w numbers each, indicating the passing points of each pair of cars.The number z on position x (1 <=x<= w) of line y (1 <=y <= e) indicates that the eastbound car y passes the westbound car x at passing point z (0 <=z <= p + 1).Westbound car x enters the road before westbound car x + 1, and eastbound car y enters the road before eastbound car y + 1. The value z = 0 indicates crossing at the west end, so car y enters the road after x has left the road. The value z = p+1, in the same way, indicates crossing at the east side.

All numbers on a line are each separated by one or more spaces.

样例输入:

2
150 1
50
1 1
1
100 1
30
3 2
2 2
1 2
0 2

样例输出:

16
48

http://acm.hdu.edu.cn/showproblem.php?pid=1596

。。就是简单的最短路。不过把最短路径的求法变了一下而已。

自己的代码。发现它跑了1500+MS,发现此题把时间放开了哦。

#include <iostream>
using namespace std;
#define N 1005
double map[N][N],prob[N];
bool visited[N];

int main(){
#ifndef ONLINE_JUDGE
	freopen("1596in.txt","r",stdin);
#endif
	int n,i,j,m,a,b,t,k;
	double max;
	while (scanf("%d",&n)!=EOF){
		for (i=0;i<n;i++)
			for (j=0;j<n;j++)
				scanf("%lf",&map[i][j]);
		scanf("%d",&m);
		for (i=0;i<m;i++){
			scanf("%d%d",&a,&b);
			a=a-1;
			b=b-1;
			memset(visited,false,sizeof(visited));
			visited[a]=true;
			for (j=0;j<n;j++)
				prob[j]=map[a][j];
			for (j=1;j<n;j++){
				max=0;
				for (k=0;k<n;k++)
					if (prob[k]>=max&&!visited[k]){
						max=prob[k];
						t=k;
					}
				visited[t]=true;
				if (t==b){
					if (prob[b]<=0)
						printf("What a pity!\n");
					else printf("%.3lf\n",prob[b]);
					break;
				}
				for (k=0;k<n;k++)
					if (!visited[k]&&prob[t]*map[t][k]>prob[k])
						prob[k]=prob[t]*map[t][k];
			}
		}
	}
	return 0;
}

解题参考:http://blog.csdn.net/operator456/article/details/8553860


  1. [email protected]

  2. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。