首页 > ACM题库 > HDU-杭电 > hdu 2680 Choose the best route-Dijkstra-[解题报告]C++
2014
02-13

hdu 2680 Choose the best route-Dijkstra-[解题报告]C++

Choose the best route

问题描述 :

One day , Kiki wants to visit one of her friends. As she is liable to carsickness , she wants to arrive at her friend’s home as soon as possible . Now give you a map of the city’s traffic route, and the stations which are near Kiki’s home so that she can take. You may suppose Kiki can change the bus at any station. Please find out the least time Kiki needs to spend. To make it easy, if the city have n bus stations ,the stations will been expressed as an integer 1,2,3…n.

输入:

There are several test cases.
Each case begins with three integers n, m and s,(n<1000,m<20000,1=<s<=n) n stands for the number of bus stations in this city and m stands for the number of directed ways between bus stations .(Maybe there are several ways between two bus stations .) s stands for the bus station that near Kiki’s friend’s home.
Then follow m lines ,each line contains three integers p , q , t (0<t<=1000). means from station p to station q there is a way and it will costs t minutes .
Then a line with an integer w(0<w<n), means the number of stations Kiki can take at the beginning. Then follows w integers stands for these stations.

输出:

There are several test cases.
Each case begins with three integers n, m and s,(n<1000,m<20000,1=<s<=n) n stands for the number of bus stations in this city and m stands for the number of directed ways between bus stations .(Maybe there are several ways between two bus stations .) s stands for the bus station that near Kiki’s friend’s home.
Then follow m lines ,each line contains three integers p , q , t (0<t<=1000). means from station p to station q there is a way and it will costs t minutes .
Then a line with an integer w(0<w<n), means the number of stations Kiki can take at the beginning. Then follows w integers stands for these stations.

样例输入:

5 8 5
1 2 2
1 5 3
1 3 4
2 4 7
2 5 6
2 3 5
3 5 1
4 5 1
2
2 3
4 3 4
1 2 3
1 3 4
2 3 2
1
1

样例输出:

1
-1

第一次提交超时了;
终点只有一个,起点有多个,想多次Dijkstra来着,结果毫无悬念地超时了
然后想起周三刘学长说多的一点——貌似就是超级汇点(为了借题需要虚构出的一个顶点)
使编号为0的虚拟超级汇点,到各个起点有一条单向的,权值无为0的边
然后从超级汇点开始查找,这样只需一次Dijkstra就OK了
#include<iostream>
using namespace std;
const int N=1005;
const int maxint=100000000;
int map[N][N],
	n;
int Dijkstra(int now,int end)
{
	int used[N],dis[N];
	for(int i=0;i<=n;i++)
	{
		dis[i]=map[now][i];
		used[i]=0;
	}
	dis[now]=0;
	used[now]=1;
	for(int i=0;i<n;i++)
	{
		int max=maxint;
		int u=now;
		for(int j=0;j<=n;j++)
			if(!used[j]&&dis[j]<max)
			{
				u=j;
				max=dis[j];
			}
			used[u]=1;
			for(int j=0;j<=n;j++)
				if(!used[j]&&map[u][j]<maxint)
				{
					int  min=dis[u]+map[u][j];
					if(min<dis[j])
					{
						dis[j]=min;
					}
				}
	}
	return dis[end];
}
int main ()
{
	int s,e,v,m,end;
		while(scanf("%d%d%d",&n,&m,&end)!=EOF)
	{
		for(int i=0;i<=n;i++)
			for(int k=0;k<=n;k++)
				map[i][k]=maxint;
		for(int i=1;i<=m;i++)
		{
		scanf("%d%d%d",&s,&e,&v);
		if(map[s][e]>v)
			map[s][e]=v;
		}
		int snum,start,ans=maxint;
		scanf("%d",&snum);
		for(int i=1;i<=snum;i++)
		{
			scanf("%d",&start);
			map[0][start]=0;
		}
		ans=Dijkstra(0,end);
		if(ans==maxint)
			printf("-1\n");
		else
			printf("%d\n",ans);
	}
	return 0;
}

解题转自:http://blog.csdn.net/meng_zy/article/details/8709788


  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  3. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3