首页 > ACM题库 > HDU-杭电 > hdu 2145 zz’s Mysterious Present-Dijkstra-[解题报告]C++
2013
12-29

hdu 2145 zz’s Mysterious Present-Dijkstra-[解题报告]C++

zz’s Mysterious Present

问题描述 :

There are m people in n cities, and they all want to attend the party which hold by zz. They set out at the same time, and they all will choose the best way they think, but due to someone take a ride, someone drive, and someone take a taxi, they have different speed. Can you find out who will get zz’s mysterious present? The first one get the party will get the present . If there are several people get at the same time, the one who stay in the city which is farther from the city where is zz at begin will get the present. If there are several people get at the same time and the distance from the city he is at begin to the city where zz is, the one who has the larger number will get the present.

输入:

The first line: three integers n, m and k. m is the total number of the people, and n is the total number of cities, and k is the number of the way.(0<n<=300, 0<m<=n, 0<k<5000)
The second line to the (k+1)th line: three integers a, b and c. There is a way from a to b, and the length of the way is c.(0<a,b<=n, 0<c<=100)
The (k+2)th line: one integer p(0<p<=n), p is the city where zz is.
The (k+3)th line: m integers. the ith people is at the place p[i] at begin.(0<p[i]<=n)
The (k+4)th line: m integers. the speed of the ith people is speed[i];(0<speed[i]<=100)
All the ways are directed.

输出:

The first line: three integers n, m and k. m is the total number of the people, and n is the total number of cities, and k is the number of the way.(0<n<=300, 0<m<=n, 0<k<5000)
The second line to the (k+1)th line: three integers a, b and c. There is a way from a to b, and the length of the way is c.(0<a,b<=n, 0<c<=100)
The (k+2)th line: one integer p(0<p<=n), p is the city where zz is.
The (k+3)th line: m integers. the ith people is at the place p[i] at begin.(0<p[i]<=n)
The (k+4)th line: m integers. the speed of the ith people is speed[i];(0<speed[i]<=100)
All the ways are directed.

样例输入:

3 1 3
1 2 2
1 3 3
2 3 1
3
2
1

样例输出:

1

#include<stdio.h>
#define MAX 0xffffff

int select[1000], dis[1000], map[1000][1000];

void ShortPath(int s, int n) //dij算法模版
{
	int i, j, k, min;
	for( i = 1; i <= n; i++)
		dis[i] = map[s][i];
	dis[s] = 0;
	select[s] = 1;
	for( i = 2; i <= n; i++)
	{
		k = -1, min = MAX;
		for( j = 1; j <= n; j++)
			if(select[j] != 1 && dis[j] < min)
			{
				k = j;
				min = dis[j];
			}
			if(k == -1)
				break;
			select[k] = 1;
			for( j = 1; j <= n; j++ )
				if( select[j] != 1 && dis[k] + map[k][j] < dis[j])
					dis[j] = dis[k] + map[k][j];
	}

}

int main()
{
	int n, m, k, p, place[1000];
	int x, y, s, flag = 0, min;
	float speed[1000], result[1000];
	while( scanf("%d%d%d", &n, &m, &k) != EOF)
	{
		int i, j;
		for( i = 1; i <= n; i++)
		{
			dis[i] = MAX;
			select[i] = 0;
			for( j = 1; j <= n; j++)
			{
				if(i == j)
					map[i][j] = 0;
				else
					map[i][j] = MAX;
			}
		}
		
		while(k--)
		{
			scanf("%d%d%d", &x, &y, &s);  //反向并单向输入
			if(map[y][x] > s)
				map[y][x] = s;
		}
		scanf("%d", &p);
		ShortPath( p, n);
		for( i = 1; i <= m; i++)
			scanf("%d", &place[i]);
		for( i = 1; i <= m; i++)
			scanf("%f", &speed[i]);
		min = 1;
		for( i = 1; i <= m; i++)   //序号筛选
		{
			result[i] = dis[place[i]]*1.0 / speed[i];
			if(result[min] > result[i])
				min = i;
			else if(result[min] == result[i])
			{
				if(dis[place[min]] <= dis[place[i]])
					min = i;
			}
		}

			if( dis[place[min]] == MAX)
				printf("No one\n");
			else
				printf("%d\n", min);
	}
	return 0;
}

解题转自:http://blog.csdn.net/acget/article/details/13765791


  1. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!