1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
| #include<stdio.h> #include<bits/stdc++.h> using namespace std; const int MAXN=50020; int dp[MAXN]; int n,m; struct E{ int u,v,w; }e[MAXN]; struct P{ int x,val; }; queue<P>q; int cmp(E x,E y){ return x.w<y.w; } int main(){ scanf("%d%d",&n,&m); int x,y,z; for(int i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); e[i]=(E){x,y,z}; } sort(e+1,e+1+m,cmp); P tmp1,tmp2; e[0].w=-1; for(int i=1;i<=m;i++){ if(e[i].w!=e[i-1].w){ while(!q.empty()){ P p=q.front();q.pop(); dp[p.x]=max(dp[p.x],p.val); } } int u=e[i].u,v=e[i].v,w=e[i].w; tmp1=(P){u,max(dp[u],dp[v]+1)}; tmp2=(P){v,max(dp[v],dp[u]+1)}; q.push(tmp1); q.push(tmp2); } while(!q.empty()){ P p=q.front();q.pop(); dp[p.x]=max(dp[p.x],p.val); } int mx=0; for(int i=0;i<n;i++){ mx=max(mx,dp[i]); } printf("%d\n",mx); return 0; }
|