The longest marathon runs from farm 2 via roads 4, 1, 6 and 3 to farm 5 and is of length 20+3+13+9+7=52.
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN = 300010;
struct Edge{
int from,to,val,next;
};
Edge edge[2*MAXN];
int head[MAXN];
int edgenum;
void init(){
memset(head,-1,sizeof(head));
edgenum=0;
}
void addEdge(int u,int v,int w)
{
edge[edgenum].from=u;
edge[edgenum].to=v;
edge[edgenum].val=w;
edge[edgenum].next=head[u];
head[u]=edgenum++;
}
int n;
int ans;
int longest;
int dis[MAXN];
bool vis[MAXN];
void BFS(int x)
{
memset(dis,0,sizeof(dis));
memset(vis,false,sizeof(vis));
queue<int> Q;
Q.push(x);
dis[x]=0;
vis[x]=true;
ans=0;
while(!Q.empty())
{
int u=Q.front();
Q.pop();
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].to;
if(!vis[v]){
if(dis[v]<dis[u]+edge[i].val){
dis[v]=dis[u]+edge[i].val;
/*if(ans<dis[v]){ 把这个放在下面的for循环中会快一些;
ans=dis[v];
longest=v;
}*/
}
vis[v]=true;
Q.push(v);
}
}
}
for(int i = 1; i <= n; i++) { //这里要注意,有的图的顶点不是从 0 开始的;比如这次的农场,没有第零个农场吧;在主函数中BFS时也要注意;
if(ans < dis[i]) {
ans = dis[i];
longest = i;
}
}
}
int main()
{
char s[2];
int m,a,b,c;
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
for(int i=0;i<m;i++)
{
scanf("%d%d%d%s",&a,&b,&c,s);
getchar();
addEdge(a,b,c);
addEdge(b,a,c);
}BFS(1); BFS(longest); //BFS(1);中的1是任意找的,也可以是2...但不能是零;
printf("%d\n",ans);
}
return 0;
}
</pre><pre name="code" class="cpp">
再帮助大家理解理解:
<pre name="code" class="cpp">#include<iostream>
#include<queue>
#define Maxn 200
using namespace std;
struct Edge{
int from,to,val,next;
}edge[Maxn]; //存储边信息的结构体
int head[Maxn]; //起点为下标存储(edge中边的位置)
int main()
{
int edgenum; //边数
memset(head,-1,sizeof(head));
//因为刚开始head不指向任何一条边的下标,所以head都为-1
cin>>edgenum; //边数
for(int i=0;i<edgenum;i++)
{
cin>>edge[i].from>>edge[i].to>>edge[i].val; //起点 终点 权重
edge[i].next=head[edge[i].from];
head[edge[i].from]=i; //不容易理解的地方
/*
利用head数组存储的是最新的(以数组下标为起点的)边的下标
并且该条边的next指向的是同样以数组下标为起点的下一条边的下标
直到下一条边的next=-1(即将所有以数组下标为起点的边都遍历了一遍)
*/
}
for(int u=1;u<10;u++) //输出图
{
cout<<"以"<<u<<"为起点的所有边的信息:"<<endl;
for(int v=head[u];v!=-1;v=edge[v].next) //遍历以u为起点的所有边的信息
cout<<edge[v].from<<" "<<edge[v].to<<" "<<edge[v].val<<endl;
}
return 0;
}