dijsktra求单源最长路径

//dij求单元最长路径

#include<bits/stdc++.h>

using namespace std;

int n,m;

int G[10001][10001];

int dist[10001];

bool visited[10001];

void dij()

{

fill(dist,dist+10001,-1);

fill(visited,visited+10001,false);

dist[m]=0;

for(int i=1;i<=n;i++)

{

int u=-1;

int max=-1;

for(int j=1;j<=n;j++)

{

if(visited[j]==false&&dist[j]>max)

{

u=j;

max=dist[j];

}

}

if(u==-1) return;

visited[u]=true;

for(int j=1;j<=n;j++)

{

if(visited[j]==false&&G[u][j]!=-1&&dist[j]<dist[u]+G[u][j])

{

dist[j]=dist[u]+G[u][j];

}

}

}

}

int main()

{

cin>>n>>m;

fill(G[0],G[0]+10001*10001,-1);

for(int i=1;i<=n-1;i++)

{

int u,v;

cin>>u>>v;

G[u][v]=G[v][u]=1;

}

dij();

//遍历dist找最大距离

int ans=-1;

for(int i=1;i<=n;i++)

{

ans=max(ans,dist[i]);

}

cout<<ans;

return 0;

}