学步园

阅读代码 注释之

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;
#define MAXV 50000
#define MAXE 100000
/*对一个图进行BFS,两次,找到直径*/
typedef struct{
	int t,w,next;
}Edge;
Edge edge[MAXE];

int n,m;
int e,head[MAXV],record[MAXV];

void addedge(int s,int t,int w){
	edge[e].t=t;
	edge[e].w=w;
	edge[e].next=head[s];
	head[s]=e++;
}///又是这样!同一个点之间的边用next找,head则用来找到s点的最近一条边
///so called 链式前向星...
int bfs(int s,int flag){
	int i,v,t;
	int tmp=0,tmpi=s;///最长路以及目的地
	queue <int>q;
	memset(record,-1,sizeof(record));///记录到达该点的路程.初始为-1表示未到过该点
	record[s]=0;///到过自己了.record其实是一个排重的标记(防止退回)
	q.push(s);
	while(!q.empty()){
		v=q.front();q.pop();
		for(i=head[v];i!=-1;i=edge[i].next){
			t=edge[i].t;
			if(record[t]==-1){
				record[t]=record[v]+edge[i].w;
				if(record[t]>tmp){
					tmp=record[t];
					tmpi=t;
				}
				q.push(t);
			}
		}
	}
	return flag?tmpi:tmp;
}

int main(){
	int a,b,w,ans;
	char c;
	while(~scanf("%d%d\n",&n,&m)){
		memset(head,-1,sizeof(head));
		e=0;
		while(m--){
			scanf("%d %d %d %c\n",&a,&b,&w,&c);
			addedge(a,b,w);
			addedge(b,a,w);
		}

		a=bfs(1,1);
		ans=bfs(a,0);
		printf("%d\n",ans);
	}
	return 0;
}

自己敲一遍~

#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int MAXN = 50005;
typedef struct edge
{
    int t,w,next;
}edge;
edge E[MAXN<<1];
int ecnt;
int head[MAXN],record[MAXN];
void insert(int s, int t, int w)
{
    E[ecnt].t = t;
    E[ecnt].w = w;
    E[ecnt].next = head[s];
    head[s] = ecnt++;
}
int bfs(int s, bool flag)
{
    int i,t,w,tmpl = 0,tmpt = s;
    memset(record,-1,sizeof(record));
    record[s] = 0;
    queue <int> q;
    q.push(s);
    while(!q.empty())
    {
        int p = q.front();
        q.pop();
        for(i = head[p];i!=-1;i = E[i].next)
        {
            t = E[i].t;
            w = E[i].w;
            if(record[t]==-1)
            {
                record[t] = record[p] + w;
                if(record[t]>tmpl)
                {
                    tmpl = record[t];
                    tmpt = t;
                }
                q.push(t);
            }
        }
    }
    return flag?tmpl:tmpt;
}

int main()
{
    int n,m,a,b,w;
    while(scanf("%d %d",&m,&n)==2)
    {
        memset(head,-1,sizeof(head));
        ecnt = 0;
        while(n--)
        {
            char c;
            scanf("%d %d %d %c",&a,&b,&w,&c);
            insert(a,b,w);
            insert(b,a,w);
        }
        m = bfs(a,0);
        printf("%d\n",bfs(m,1));
    }
}