hdu 1546 Idiomatic Phrases Game

http://acm.hdu.edu.cn/showproblem.php?pid=1546
 1 #include <cstdio>
 2 #include <iostream>
 3 #include <queue>
 4 #include <cstring>
 5 #include <algorithm>
 6 #define maxn 1001
 7 using namespace std;
 8 const int inf=1<<30;
 9 
10 int a[maxn],n;
11 int g[maxn][maxn];
12 char str[maxn][maxn];
13 int dis[maxn];
14 bool vis[maxn];
15 
16 void spfa()
17 {
18     queue<int>q;
19     memset(vis,false,sizeof(vis));
20     for(int i=0; i<=n; i++) dis[i]=inf;
21     dis[0]=0;
22     vis[0]=true;
23     q.push(0);
24     while(!q.empty())
25     {
26         int u=q.front(); q.pop();
27         vis[u]=false;
28         for(int i=0; i<n; i++)
29         {
30             if(g[u][i]!=inf&&dis[i]>dis[u]+g[u][i])
31             {
32                 dis[i]=dis[u]+g[u][i];
33                 if(!vis[i])
34                 {
35                     q.push(i);
36                     vis[i]=true;
37                 }
38             }
39         }
40     }
41 }
42 
43 int main()
44 {
45     while(scanf("%d",&n)!=EOF)
46     {
47         if(n==0) break;
48         for(int i=0; i<n; i++)
49         {
50             cin>>a[i]>>str[i];
51         }
52         for(int i=0; i<n; i++)
53         {
54             for(int j=0; j<n; j++)
55             {
56                 if(i==j) g[i][j]=0;
57                 else g[i][j]=inf;
58             }
59         }
60         for(int i=0; i<n; i++)
61         {
62             for(int j=0; j<n; j++)
63             {
64                 if(i==j) continue;
65                 bool flag=false;
66                 int k=strlen(str[i]);
67                 for(int c=0; c<4; c++)
68                 {
69                     if(str[i][k+c-4]!=str[j][c])
70                     {
71                         flag=true;
72                         break;
73                     }
74                 }
75                 if(!flag)
76                 {
77                     g[i][j]=a[i];
78                 }
79             }
80         }
81         /*for(int i=0; i<n; i++)
82         {
83             for(int j=0; j<n; j++)
84             {
85                 printf("%d ",g[i][j]);
86             }
87             printf("
");
88         }*/
89         spfa();
90         if(dis[n-1]==inf) printf("-1
");
91         else printf("%d
",dis[n-1]);
92     }
93     return 0;
94 }
View Code