hdu 2112 HDU Today（Dijkstra+字典树）

Problem Description

经过锦囊相助，海东集团终于度过了危机，从此，HDU的发展就一直顺风顺水，到了2050年，集团已经相当规模了，据说进入了钱江肉丝经济开发区500强。这时候，XHD夫妇也退居了二线，并在风景秀美的诸暨市浬浦镇陶姚村买了个房子，开始安度晚年了。这样住了一段时间，徐总对当地的交通还是不太了解。有时很郁闷，想去一个地方又不知道应该乘什么公交车，在什么地方转车，在什么地方下车（其实徐总自己有车，却一定要与民同乐，这就是徐总的性格）。徐总经常会问蹩脚的英文问路：“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，表示输入结束。

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

Sample Output

50

用字典树给站名编号，用Dijkstra求最短路。注意起点和终点可能相同。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int mx=30000000;
 6 int v[200],ans[200];
 7 struct p
 8 {
 9     int next[200];
10     int v;
11     void ff()
12     {
13         memset(next,-1,sizeof(next));
14         v=0;
15     }
16 };p tree[100000];
17 int n,pn,k;
18 int map[205][205];
19 int f(char *s)
20 {
21     int i,j=0,su;
22     for (i=0;s[i];i++)
23     {
24         su=s[i]-'A';
25         if (tree[j].next[su]==-1)
26         {
27             pn++;
28             tree[j].next[su]=pn;
29             tree[pn].ff();
30         }
31         j=tree[j].next[su];
32     }
33     if (tree[j].v) return tree[j].v;
34     else
35     {
36         k++;
37         return tree[j].v=k-1;
38     }
39 }
40 void djik(int x)
41 {
42     int i,p,mn;
43     v[x]=1;
44     for (i=1;i<k;i++) ans[i]=map[i][x];
45     while (1)
46     {
47         p=x;
48         mn=mx;
49         for (i=1;i<k;i++)
50         {
51             if (!v[i]&&ans[i]<mn)
52             {
53                 p=i;
54                 mn=ans[i];
55             }
56         }
57         if (p==x) return ;
58         v[p]=1;
59         for (i=1;i<k;i++)
60         {
61             if (!v[i]&&ans[i]>ans[p]+map[p][i])
62                 ans[i]=ans[p]+map[p][i];
63         }
64     }
65 }
66 int main()
67 {
68    int i,j,a,b,t,x,y;
69    char s1[40],s2[40];
70    while (~scanf("%d",&n))
71    {
72        if (n==-1) break;
73        scanf("%s %s",&s1,&s2);
74        k=1;
75        pn=0;
76        tree[pn].ff();
77        x=f(s1);
78        y=f(s2);
79        for (i=1;i<=200;i++)
80        for (j=1;j<=200;j++)
81        if (i==j) map[i][j]=0;
82        else map[i][j]=mx;
83        while (n--)
84        {
85            scanf("%s %s %d",&s1,&s2,&t);
86            a=f(s1);
87            b=f(s2);
88            if (map[a][b]>t) map[a][b]=map[b][a]=t;
89        }
90        memset(v,0,sizeof(v));
91        djik(x);
92        if (ans[y]==mx) printf("-1
");
93        else printf("%d
",ans[y]);
94    }
95    return 0;
96 }

hdu 2112 HDU Today（Dijkstra+字典树）

相关推荐