【题目描述】

【思路】

如果是有向图，那么可以把边按照从小到大排序，然后设 $dp[i]$ 以 $i$ 为终点的最长距离。有 dp[u]=max{dp[u],dp[v]+1∣(u,v)∈E}dp[u]=max\{dp[u],dp[v]+1|(u,v)\in E\}dp[u]=max{

dp[u],dp[v]+1∣(u,v)∈E}

而在无向图中，对于无向边 $(u,v)$ 有

dp[u]=max{dp[u],dp[v]+1}dp[u]=max\{dp[u],dp[v]+1\}dp[u]=max{

dp[u],dp[v]+1}

dp[v]=max{dp[v],dp[u]+1}dp[v]=max\{dp[v],dp[u]+1\}dp[v]=max{

dp[v],dp[u]+1}

因为 $dp$ 是一个数组，两个状态转移方程的先后顺序会有所影响。

所以另外用一个数组 $tmp$，$tmp[i]$ 记录上一次更新后时候的 $dp[i]$

那么就有：

dp[u]=max{dp[u],tmp[v]+1}dp[u]=max\{dp[u],tmp[v]+1\}dp[u]=max{

dp[u],tmp[v]+1}

dp[v]=max{dp[v],tmp[u]+1}dp[v]=max\{dp[v],tmp[u]+1\}dp[v]=max{

dp[v],tmp[u]+1}

对边权升序排序，对于每一种权值进行统一处理

#include
    
     using namespace std;const int maxn=50005;struct Edge{	int from,to,dist;	Edge(int f=0,int t=0,int d=0):from(f),to(t),dist(d){}	bool operator<(const Edge& e)const{		return dist