**
旅行
**
Time Limit: 1000 MS Memory Limit: 32768 K
Total Submit: 50(25 users) Total Accepted: 20(20 users) Rating: Special Judge: No
Description
“04.24，和Sakura去东京天空树，世界上最暖和的地方天空树的顶上。”
“04.26，和Sakura去明治神宫，有人在那里举办婚礼。”
“04.25，和Sakura去迪士尼，鬼屋很可怕，但是有Sakura在，所以不可怕。”
“Sakura最好了。”
——江南 《龙族》
绘梨衣和路明非今天要从迪士尼前往天空树，但他们的钱不多了，所以能省则省，他们现在有一个地图上面有n个景点和m条景点之间的路，每条路坐车都需要一定的钱数，现在他们求助于你，请你帮他们计算下从当前地点到目的地最少需要的钱数。
Input
有多组数据，每组数据第一行有两个数字2<=n<=30000，1<=m<=30000。
接下来n行输入n个地名。
接下来m行每行有两个字符串(长度不超过20)和一个数字，代表两地之间的坐车的费用。
接下来一行输入两个字符串分别代表起点和终点。
Output
一个int数代表最少需要的钱数。
数据保证不会超过int型范围。
Sample Input
2 1
disney
TokyoSkyTree
disney TokyoSkyTree 1
disney TokyoSkyTree
Sample Output
1
裸最短路，用Map对应上所有地名即可
#include<stdio.h>///优先队列优化
#include<string.h>
#include<vector>
#include<queue>
#include<string>
#include<map>
#define ll long long
using namespace std;
const int N=30004;
const int MAX=0x7fffffff;
ll dist[N];///记录到达每个节点的最短路
ll n,m,flag;
struct Edge
{
int to,val;///点的标号以及到达此点需要的权值
Edge(ll a=0,ll b=0):to(a),val(b){}///结构体构造函数
bool operator <(const Edge &a)const///重载运算符
{
if(val==a.val)return to<a.to;
return val>a.val;
}
};
vector<Edge>v[N];///(结构体类型)动态数组做邻接矩阵
void dijkstra(int s)
{
// memset(dist,0x3f,sizeof(dist));///一开始到达所有节点的路程都是inf
for(int i=0;i<=n;i++)dist[i]=1e18;
flag=dist[0];///用于判断无法到达的情况(-1)
dist[s]=0;///到达起点的最短路为0
priority_queue<Edge>q;///优先队列优化
q.push(Edge(s,0));///将起始节点放入队列中
while(!q.empty())
{
Edge top=q.top();
q.pop();
for(int i=0;i<v[top.to].size();i++)///遍历所有从当前点出发到达的所有节点
{
Edge tmp=v[top.to][i];
if(dist[tmp.to]>top.val+tmp.val)///用当前节点松弛目的节点的最短路
{
dist[tmp.to]=top.val+tmp.val;
q.push(Edge(tmp.to,dist[tmp.to]));///每次投入队列中的结构体都是直接构造的，并不是原先就存在的
} ///投入一个可以到达的点，权值取当前到达节点的已知最短路
}
}
}
int main()
{
map<string,int>mp;
while(scanf("%d%d",&n,&m)!=EOF)
{
char name[25];
for(int i=0;i<n;i++)
{
scanf("%s",name);
mp[name]=i;
}
char from[25],to[25];
ll val;
for(int i=0;i<m;i++)
{
scanf("%s %s %lld",from,to,&val);
v[mp[from]].push_back(Edge(mp[to],val));
v[mp[to]].push_back(Edge(mp[from],val));
}
scanf("%s %s",from,to);
dijkstra(mp[from]);
printf("%lld
",dist[mp[to]]);
}
}