HDU-2112 HDU Today 最短路之无病呻吟

绝地灬酷狼 2022-01-06 14:43 185阅读 0赞

# HDU Today #

**Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 3581 Accepted Submission(s): 855**

Problem Description

经过锦囊相助，海东集团终于度过了危机，从此，HDU的发展就一直顺风顺水，到了2050年，集团已经相当规模了，据说进入了钱江肉丝经济开发区500强。这时候，XHD夫妇也退居了二线，并在风景秀美的诸暨市浬浦镇陶姚村买了个房子，开始安度晚年了。  
这样住了一段时间，徐总对当地的交通还是不太了解。有时很郁闷，想去一个地方又不知道应该乘什么公交车，在什么地方转车，在什么地方下车（其实徐总自己有车，却一定要与民同乐，这就是徐总的性格）。  
徐总经常会问蹩脚的英文问路：“Can you help me?”。看着他那迷茫而又无助的眼神，热心的你能帮帮他吗？  
请帮助他用最短的时间到达目的地（假设每一路公交车都只在起点站和终点站停，而且随时都会开）。

Input

输入数据有多组，每组的第一行是公交车的总数N(0<=N<=10000)；  
第二行有徐总的所在地start，他的目的地end；  
接着有n行，每行有站名s，站名e，以及从s到e的时间整数t(0<t<100)(每个地名是一个长度不超过30的字符串)。  
note：一组数据中地名数不会超过150个。  
如果N==-1，表示输入结束。

Output

如果徐总能到达目的地，输出最短的时间；否则，输出“-1”。

Sample Input

6  
xiasha westlake  
xiasha station 60  
xiasha ShoppingCenterofHangZhou 30  
station westlake 20  
ShoppingCenterofHangZhou supermarket 10  
xiasha supermarket 50  
supermarket westlake 10  
\-1

Sample Output

50  
  
  
Hint:  
The best route is:  
xiasha->ShoppingCenterofHangZhou->supermarket->westlake  
  
  
虽然偶尔会迷路，但是因为有了你的帮助  
\*\*和\*\*从此还是过上了幸福的生活。  
  
――全剧终――

昨天学了下C++中的一些东西，都是用来减少代码量的，即利用别人已经写好的类模板加之写好的算法函数，调用即可。

总结如下：

queue< Type > 变量名 这是类模板（不知道这样称呼是否是对的），尖括号里面是类型，定义好之后，例如：queue< int > 就已经是一个类了，这个类里面有很多的函数可供使用，例如: 变量名为 x, x. size( ), x. front( ), x. pop( ), x. push( insert ) 等等，后面的也才不多有这些函数。

map< Type1, Type2 > 变量名 提供一个映射函数，其存储结构是对所输入的 Key 构造一棵红黑树，加快了寻找的时间，当然，如果Type1是一个对象的话，还要根据需要重载 < 操作符， 这时因为系统在进行排序时，调用的就是两个类之间的 < 操作符进行比较，不然抽象数据类型之间是无法进行比较的， 有个重要的操作x. erase( Type )， 它能将指定的元素进行释放。

priority\_queue< Type > 变量名 这里就是注意一下建立小顶堆和大顶堆的不同操作就是在重载 < 操作符时，前者是将内部进行 > 判定，后者是 < 判定，然后就是取堆顶元素的操作是 x. top( )， 判空函数 x. empty( )。

vector< Type > 变量名 其主要优势就是它是自增的一个空间，无需使用者在意所加数据的数量，函数有 x. push\_back( insert ), x. clear( )支持下标访问。

迭代器：对于以上所介绍的所有容器，都会有相应的迭代器去使用，迭代器一般是针对某一类型来的，例如 vector< int >:: iterotar it, 前面的整个是类型名，后面的it是变量名，it只能自增运算，it++， 而不能 it+=1；一般会这样使用 for( it= x. begin( ); it!= x. end( ); it++ ) \{ ... \}

此题代码如下:

#include <iostream>
    #include <queue>
    #include <algorithm>
    #include <vector>
    #include <map>
    #include <stdio.h>
    #define INF 0x7fffffff
    
    using namespace std;
    
    struct inf
    {
    	int x, cost;
    	inf set( int e, int c )
    	{
    		x= e, cost= c;
    		return *this;
    	}
    	bool operator < ( const inf &t ) const
    	{
    		return cost> t. cost;
    	}
    }info;
    
    map< string, int > mp;  // 前面相当与x，右面相当与f( x )的函数值
    vector< inf > vec[155];
    
    int hash[155], dis[155];
    
    int Dijkstra( string beg, string end )
    {
    	int Ibeg= mp[beg], Iend= mp[end];
    	priority_queue< inf > q;
    	q. push( info. set( Ibeg, 0 ) );
    	for( int i= 0; i<= 150; ++i )
    	{
    		hash[i]= 0;
    		dis[i]= INF; 
    	}
    	while( !q. empty(  ) )
    	{ 
    		info= q. top(  );
    		q. pop(  );
    		int pos= info. x;
    		dis[pos]= info. cost;
    		hash[pos]= 1; 
    		if( pos== Iend )
    		{
    			return dis[pos];
    		} 
    		for( int j= 0; j< vec[pos]. size(  ); ++j )
    		{
    			int tx= vec[pos][j]. x, tc= vec[pos][j]. cost; 
    			if( !hash[tx]&& dis[pos]+ tc < dis[tx] )
    			{
    				dis[tx]= dis[pos]+ tc;
    				q. push( info. set( tx, dis[tx] ) ); 
    			}
    		}
    	}
    	return -1;
    }
    
    int main(  )
    {
    	int N;
    	while( cin>> N, N!= -1 )
    	{
    		int cnt= 0;
    		mp. clear(  );
    		for ( int i = 0; i <= 150; ++ i ) 
    		    vec[i].clear (  );
    		char beg[35], end[35];
    		scanf( "%s %s", beg, end );
    		if( mp. count( beg )== 0 ) mp[beg]= cnt++;
    		if( mp. count( end )== 0 ) mp[end]= cnt++;
    		for( int i= 0; i< N; ++i )
    		{
    			char t1[35], t2[35];  /**/  int cost;
    			scanf( "%s %s %d", t1, t2, &cost );
    			if( !mp. count( t1 ) ) mp[t1]= cnt++;
    			if( !mp. count( t2 ) ) mp[t2]= cnt++;
    			vec[mp[t1]]. push_back( info. set( mp[t2], cost ) );
    			vec[mp[t2]]. push_back( info. set( mp[t1], cost ) );
    		}
    		cout<< Dijkstra( beg, end )<< endl;
    	}
    }

转载于:https://www.cnblogs.com/Lyush/archive/2011/07/29/2120611.html