本文主要是介绍hdu 4460 Friend Chains(最短路径，spfa)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：http://acm.hdu.edu.cn/showproblem.php?pid=4460
做这道题前关于最短路径只会Dijkstra，所以呢，TLE...参考了更好的spfa算法，原来他用队列和标记数组进行优化，标记过了的点不会被放进队列了，函数是针对从队列中的取出的点进行相连点发散遍历，且每次遍历如果发现了更短的路径都及时的把目的地相应点标记了，这样相比Dijkstra的从头至尾遍历找一条最短路径标记目的地的相应点，再遍历更新要快。但仅仅这样还不够，我试了试仍然TLE...于是看看别人的代码，用优化了的邻接矩阵vector<int> v来保存能联系的点，这样勉强过了。
spfa:
#include <iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<cstring>
#include<string>
#include<queue>
using namespace std;
const int INF=0x3f3f3f3f,maxn=1005;
int n,m,ans;
string s,s2;
int imap[maxn][maxn];
map<string,int> mp;
vector<int> v[1010];
int dis[maxn];
bool tag[maxn];
queue<int> que;
void spfa(int s){memset(tag,0,sizeof(tag));memset(dis,0,sizeof(dis));for(int i=1;i<=n;i++) dis[i]=INF;tag[s]=1;que.push(s);dis[s]=0;while(!que.empty()){int t=que.front();que.pop();tag[t]=0;for(int i=0;i<v[t].size();i++){if(dis[v[t][i]]>dis[t]+1){dis[v[t][i]]=dis[t]+1;if(!tag[v[t][i]]){ que.push(v[t][i]); tag[v[t][i]]=1; }}}}for(int i=1;i<=n;i++){ans=ans>dis[i]?ans:dis[i];}
}
int main()
{//freopen("cin.txt","r",stdin);while(cin>>n&&n){int i,j;mp.clear();for(i=1; i<=n; i++)v[i].clear();for(i=1;i<=n;i++){cin>>s;mp[s]=i;}//showmp();scanf("%d",&m);ans=0;for(i=0;i<m;i++){cin>>s>>s2;int a=mp[s],b=mp[s2];v[a].push_back(b);v[b].push_back(a);}//showimap();for(i=1;i<=n;i++){spfa(i);}if(ans>n-1)printf("-1\n");else printf("%d\n",ans);}return 0;
}
TLE的Dijkstra:
#include <iostream>
#include<cstdio>
#include<map>
#include<cstring>
using namespace std;
const int INF=0x3f3f3f3f,maxn=1005;
int n,m;
char s[15];
char str[1005][15];
int imap[maxn][maxn];
struct cmp{bool operator()(char *s1,char *s2){return strcmp(s1,s2)<0;}
};
map<char *,int,cmp> mp;
int dis[maxn];
bool tag[maxn];
void Dijkstra(int s){memset(tag,0,sizeof(tag));memset(dis,0,sizeof(dis));tag[s]=1;for(int i=1;i<=n;i++){dis[i]=imap[s][i];}for(int i=1;i<n;i++){int k=0,mmin=INF;for(int j=1;j<=n;j++){if(!tag[j]&&mmin>dis[j]){mmin=dis[j];k=j;}}if(k==0)return ;tag[k]=1;for(int j=1;j<=n;j++){if(!tag[j]&&dis[j]>dis[k]+imap[k][j])dis[j]=dis[k]+imap[k][j];}}
}
void inital(){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){imap[i][j]=INF;}}
}
void showimap(){int i,j;for(i=1;i<=n;i++){for(j=1;j<=n;j++){cout<<imap[i][j]<<" ";}cout<<endl;}
}
void showdis(){for(int j=1;j<=n;j++)cout<<dis[j]<<" "; cout<<endl;
}
void showmp(){for(map<char *,int,cmp>::iterator ix=mp.begin();ix!=mp.end();ix++){cout<<ix->first<<" "<<ix->second<<endl;}
}
int main()
{//freopen("cin.txt","r",stdin);while(cin>>n&&n){int i,j;for(i=1;i<=n;i++){scanf("%s",str[i]);mp.insert(make_pair(str[i],i));}//不能只用一个字符串来编辑mp: cin>>str; mp.insert(make_pair(str,i));//showmp();scanf("%d",&m);int ans=0;inital();for(i=0;i<m;i++){char s2[15];scanf("%s%s",s,s2);imap[mp[s]][mp[s2]]=1;imap[mp[s2]][mp[s]]=1;}//showimap();for(i=1;i<n;i++){Dijkstra(i);for(j=i+1;j<=n;j++){ans=ans>dis[j]?ans:dis[j];}}if(ans>n-1)printf("-1\n");else printf("%d\n",ans);}return 0;
}另外，写的过程中发现了一个奇怪的错误：error C2679: 二进制“>>”: 没有找到接受“std::string”类型的右操作数的运算符(或没有可接受的转换)：查了查知道了，头文件的事儿。“ 把#include "String.h" 改成#include<string> "string.h"是C语言中的用法，没有运算符的重载，而C++中用<string>，新添了运算符的重载 。”
这篇关于hdu 4460 Friend Chains(最短路径，spfa)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
