本来是拿来复习一下map的，没想搞了半天，一直wa，最后发现预处理没有处理到所有的点
就是个最短路
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 虽然偶尔会迷路，但是因为有了你的帮助
**和**从此还是过上了幸福的生活。 ――全剧终――
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
const int maxint=;
//printf("----\n");
using namespace std;
int m,t;
int tot=;
map<string,int> st;
int c[][],dist[];
void dijkstra(int u,int n)
{
//printf("%d\n",n);
bool vis[];
for(int i=;i<=n;i++)
{
vis[i]=;
dist[i]=c[u][i];
}
vis[u]=;
for(int i=;i<=n;i++)
{
int temp=maxint;
int k=u;
for(int j=;j<=n;j++)
{
if(!vis[j]&&dist[j]<temp)
{
temp=dist[j];
k=j;
}
}
if(temp==maxint) break;
vis[k]=;
for(int j=;j<=n;j++)
{
if(!vis[j]&&c[k][j]<maxint)
{
if(dist[k]+c[k][j]<dist[j])
dist[j]=dist[k]+c[k][j];
}
}
}
}
int main()
{
int i,j,k,n;
//freopen("1.in","r",stdin);
while(scanf("%d",&n)!=EOF)
{
bool flag=;
if(n==-) break;
st.clear();
char s[],e[];
scanf("%s%s",s,e);
if(strcmp(s,e)==)
{
flag=;
}
st[s]=;
st[e]=;
tot=;
for(i=;i<=;i++)
{
for(j=;j<=;j++) c[i][j]=c[j][i]=((i==j)?:maxint);
}
for(i=;i<=;i++)
{
dist[i]=maxint;
}
for(i=;i<=n;i++)
{
int w;
scanf("%s%s%d",s,e,&w);
if(!st[s]) st[s]=tot++;
if(!st[e]) st[e]=tot++;
c[st[s]][st[e]]=c[st[e]][st[s]]=w;
}
dijkstra(,tot);
if(flag) printf("0\n");
else if(dist[]==maxint) printf("-1\n");
else
printf("%d\n",dist[]);
}
return ;
}
2015-04-24：这个是kuangbin模板的，检测了一下，算法里的起点是从0开始的，那个优化代码不知道怎么就wa了，等刷到kuang大神的最短路再看吧
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
#define MOD 1000000007
const double eps=1e-;
#define cl(a) memset(a,0,sizeof(a))
#define ts printf("*****\n");
const int MAXN=;
int n,m,tt;
#define typec int
const typec INF=;//防止后面溢出，这个不能太大
int c[MAXN][MAXN],tot=,dist[];
bool vis[MAXN];
int pre[MAXN];
void Dijkstra(typec cost[][MAXN],typec lowcost[],int n,int beg)
{
for(int i=;i<=n;i++)
{
lowcost[i]=INF;vis[i]=false;pre[i]=-;
}
lowcost[beg]=;
for(int j=;j<n;j++)
{
int k=-;
int Min=INF;
for(int i=;i<=n;i++)
if(!vis[i]&&lowcost[i]<Min)
{
Min=lowcost[i];
k=i;
}
if(k==-)break;
vis[k]=true;
for(int i=;i<=n;i++)
if(!vis[i]&&lowcost[k]+cost[k][i]<lowcost[i])
{
lowcost[i]=lowcost[k]+cost[k][i];
pre[i]=k;
}
}
}
map<string,int> st;
int main()
{
int i,j,k;
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
while(scanf("%d",&n)!=EOF)
{
bool flag=;
if(n==-) break;
st.clear();
char s[],e[];
scanf("%s%s",s,e);
if(strcmp(s,e)==)
{
flag=;
}
st[s]=;
st[e]=;
tot=;
for(i=;i<=;i++)
{
for(j=;j<=;j++) c[i][j]=c[j][i]=((i==j)?:INF);
}
for(i=;i<=;i++)
{
dist[i]=INF;
}
for(i=;i<=n;i++)
{
int w;
scanf("%s%s%d",s,e,&w);
if(!st[s]) st[s]=tot++;
if(!st[e]) st[e]=tot++;
c[st[s]][st[e]]=c[st[e]][st[s]]=w;
}
Dijkstra(c,dist,tot,);
if(flag) printf("0\n");
else if(dist[]==INF) printf("-1\n");
else
printf("%d\n",dist[]);
}
}