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?”。看着他那迷茫而又无助的眼神，热心的你能帮帮他吗？
请帮助他用最短的时间到达目的地（假设每一路公交车都只在起点站和终点站停，而且随时都会开）。
这样住了一段时间，徐总对当地的交通还是不太了解。有时很郁闷，想去一个地方又不知道应该乘什么公交车，在什么地方转车，在什么地方下车（其实徐总自己有车，却一定要与民同乐，这就是徐总的性格）。
徐总经常会问蹩脚的英文问路：“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，表示输入结束。
第二行有徐总的所在地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
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
虽然偶尔会迷路，但是因为有了你的帮助
**和**从此还是过上了幸福的生活。
――全剧终――
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;
}
}