hdu 4460 friend chains spfa 最短路里面的最长路

题意不再赘述。。。

连接http://acm.hdu.edu.cn/showproblem.php?pid=4460

此题直接郁闷致死。。。。

比赛的时候用的是floyd然后直接超时。。。当时闪过spfa的想法，但是觉得如果是一个循环spfa话也会超时。。。

今天试了一下。。。果然超时= =。。。郁闷啊亲。。。然后优化了一下，用一个邻接表去存边。

一开始忽略了一点就是-1的输出。。。

代码。

View Code

  1 #include <stdio.h>
  2 #include <iostream>
  3 #define inf 10000
  4 #include <map>
  5 using namespace std;
  6 
  7 map<string,int>str;//但是王林说用map，觉得无非就是搜两下，没那个必要。。。。过会试一下
  8 int n,ans;
  9 int dis[1005][1005];
 10 int q[1000005];
 11 struct node
 12 {
 13     int u[1005];
 14     int utop;
 15 }edge[1005];
 16 void init(int n)//边的初始化
 17 {
 18     int i,j;
 19     for(i = 0;i < n;i++)
 20     {
 21         for(j = i+1;j < n;j++)
 22         dis[j][i] = dis[i][j] = inf;
 23         dis[i][i] = 0;
 24     }
 25 }
 26 void spfa(int pre)
 27 {
 28     int i,vis[10005] = {0},f,r;
 29     int d[1005];
 30     f = r = 0;
 31     q[r++] = pre;
 32     vis[pre] = 1;
 33     for(i = 0;i < n;i++)//这步不能用dis赋值啊亲，我找了好久。。。发现那样的话第一次就没有入栈 的= =，一边循环直接跳出
 34     d[i] = inf;
 35     d[pre] = 0;
 36 
 37     while(f<r)
 38     {
 39         int temp;
 40         temp = q[f++];
 41 
 42         for(i = 0;i < edge[temp].utop;i++)
 43         {
 44             if(d[edge[temp].u[i]] > dis[temp][edge[temp].u[i]] + d[temp] && dis[temp][edge[temp].u[i]] + d[temp] <= 7)
 45             {
 46                 dis[pre][edge[temp].u[i]] = d[edge[temp].u[i]] = dis[temp][edge[temp].u[i]] + d[temp];
 47 
 48                 if(!vis[edge[temp].u[i]])
 49                 {
 50                     q[r++] = edge[temp].u[i];
 51                     vis[edge[temp].u[i]] = 1;
 52                 }
 53             }
 54         }
 55     }
 56 }
 57 int main()
 58 {
 59     int i,j;
 60     string s,s1,s2;
 61     int m;
 62     while(scanf("%d",&n)&&n)
 63     {
 64         ans = -1;
 65         int hash[1005] = {0};
 66         str.clear();
 67         for(i = 0;i < n;i++)
 68         {
 69             cin>>s;
 70             str[s] = i;
 71         }
 72         init(n);
 73         scanf("%d",&m);
 74         while(m--)
 75         {
 76             cin>>s1>>s2;;
 77             int a,b;
 78             a = str[s1];
 79             b = str[s2];
 80             if(hash[a] == 0)//用一个hash 来看是否访问过，对邻接表进行初始化
 81             hash[a] = 1,edge[a].utop = 0;
 82             if(hash[b] == 0)
 83             hash[b] = 1,edge[b].utop = 0;
 84             edge[a].u[edge[a].utop++] = b;
 85             edge[b].u[edge[b].utop++] = a;
 86             dis[a][b] = dis[b][a] = 1;
 87         }
 88 
 89         for(i = 0;i < n;i++)//遍历
 90         spfa(i);
 91         for(i = 0;i < n;i++)
 92         {
 93             for(j = i+1;j < n;j++)//减少时间
 94             if(ans < dis[i][j])
 95             ans = dis[i][j];
 96         }
 97         if(ans > 7)//如果有大于7的话说明有连接不上的。其实就是ans初值inf
 98         puts("-1");
 99         else
100         printf("%d\n",ans);
101     }
102 }