map+dijkstra+邻接表

hdu2112
最短路

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;

struct Edge{
	int to;
	int v;
	Edge(int t,int vv):to(t),v(vv){} 
};

map<string,int>mp;
vector<Edge> G[200];
int mk=1;
int dis[200];
int vis[200];
const int inf=0x3fffffff;

int dijkstra(int s,int end)
{
	for(int i=0;i<mk;i++)
	{
		dis[i]=inf;
		vis[i]=false;
	}
	
	dis[s]=0;
	vis[s]=true;
	
	for(int i=0;i<G[s].size();i++)
	{
		Edge e=G[s][i];
		int to=e.to;
		int v=e.v;
		dis[to]=v;
	}
	
	for(int i=0;i<mk;i++)
	{
		int mx=inf,id;
		for(int j=1;j<mk;j++)
		{
			if(dis[j]<mx&&!vis[j])
			{
				mx=dis[j];
				id=j;
			}
		}
		if(mx==inf)break;
		vis[id]=true;
		for(int j=0;j<G[id].size();j++)
		{
			Edge e=G[id][j];
			int to=e.to;
			int v=e.v;
			if(dis[id]+v<dis[to]&&!vis[to])
			{
				dis[to]=dis[id]+v;
			}
		}
	}
	return dis[end];
}

using namespace std;
int main()
{
	int n;
	string s,e,a,b;
	int v;

	while(cin>>n)
	{
		mp.clear();
		for(int i=0;i<155;i++)G[i].clear();
		mk=1;
		if(n==-1)break;
		cin>>s>>e;
		mp[s]=mk++;
		if(s!=e)mp[e]=mk++;
		for(int i=0;i<n;i++)
		{
			cin>>a>>b>>v;
			if(!mp[a])mp[a]=mk++;
			if(!mp[b])mp[b]=mk++;
			G[mp[a]].push_back(Edge(mp[b],v));
			G[mp[b]].push_back(Edge(mp[a],v));
			
		}
		int ans=dijkstra(mp[s],mp[e]);
		if(ans==inf)cout<<-1<<endl;
		else
		cout<<ans<<endl;
	}
	return 0;
}