﻿HDU 2112 HDU Today(Floyd)-Ocrosoft

# HDU Today

Time Limit: 15000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 25387    Accepted Submission(s): 6140

Problem Description

Input

note：一组数据中地名数不会超过150个。

Output

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

**和**从此还是过上了幸福的生活。

――全剧终――
```

Author
lgx

Solution

```#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ms(a) memset(a,0,sizeof(a))
#define INF INT_MAX
#define MAXN 150+10
using namespace std;
int edge[MAXN][MAXN];
char mp[MAXN][35],st[35],tt[35],s[35],t[35];
int mp_size;
int find_mp(bool s_t)
{
for(int i=1;i<mp_size;i++)
if(!strcmp(mp[i],s_t?t:s))
return i;
return -1;
}
int main()
{
int n,m,r;
while(cin>>n&&n+1)
{
cin>>st>>tt;
mp_size=1;
strcpy(mp[mp_size++],st);
strcpy(mp[mp_size++],tt);
for(int i=1; i<=MAXN-1; i++) //初始化
for(int j=1;j<=MAXN-1;j++)
edge[i][j]=INF;
for(int i=1; i<=n; i++)
{
cin>>s>>t>>r;
int a=find_mp(0),b=find_mp(1);
if(a==-1)strcpy(mp[mp_size++],s),a=mp_size-1;
if(b==-1)strcpy(mp[mp_size++],t),b=mp_size-1;
if(edge[a][b]>r)
edge[a][b]=edge[b][a]=r;
}
if(!strcmp(st,tt))
{
printf("0\n");
continue;
}
//Floyd
for(int k=1; k<mp_size; k++)
for(int i=1; i<mp_size; i++)
for(int j=1; j<mp_size; j++)
if(edge[i][k]<INF&&edge[k][j]<INF)
edge[i][j]=min(edge[i][j],edge[i][k]+edge[k][j]);
printf("%d\n",edge[1][2]==INF?-1:edge[1][2]);
}
return 0;
}
```