題意不再贅述。。。

連接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 }

轉載于:https://www.cnblogs.com/0803yijia/archive/2012/11/08/2761693.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的hdu 4460 friend chains spfa 最短路里面的最长路的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。