题意：给出源点和边，边权为1，让你求从源点出发的最长路径，求出路径长度和最后地点，若有多组，输出具有最小编号的最后地点。
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <queue>using namespace std; const int maxn=110; int n,s,tot; //n:点的个数，s:源点 int dist[maxn]; //存储该点到源点的最长路径 int head[maxn]; int vis[maxn]; //用来在SPFA算法中标记点是否在队列中 struct Edge{int to,next; }edge[5050];void add(int u,int v){edge[tot].next=head[u];edge[tot].to=v;head[u]=tot++; } void SPFA(){queue<int> q;int tmp,u,v;dist[s]=0;q.push(s);vis[s]=1;while(!q.empty()){u=q.front();q.pop();vis[u]=0;//对u的所有出边的端点进行松弛操作，如果可以经过u使得源点到v的路径变长，则更新for(int k=head[u];k!=-1;k=edge[k].next){v=edge[k].to;if(dist[u]+1>dist[v]){dist[v]=dist[u]+1;//若点v不在队列里，则加入到队列中if(!vis[v]){q.push(v);vis[v]=1;}}}} } int main() {int u,v,t=0;while(scanf("%d",&n)!=EOF){if(n==0)break;memset(head,-1,sizeof(head));memset(dist,0,sizeof(dist));memset(vis,0,sizeof(vis));tot=0;scanf("%d",&s);while(scanf("%d%d",&u,&v)!=EOF){if(u==0 && v==0)break;add(u,v);}SPFA();int ans=200,length=0;for(int i=1;i<=n;i++){if(dist[i]>length){length=dist[i];ans=i;}else if(dist[i]==length && i<ans){ans=i;}}printf("Case %d: The longest path from %d has length %d, finishing at %d.\n",++t,s,length,ans);printf("\n"); //ÉÙÁË»»ÐУ¬WA¡£¡£¡£ }return 0; }