757F - Team Rocket Rises Again - CodeForces Solution

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll dis[301000];
int n,m,s;
struct ed{
	int v;ll w;
	bool operator < (const ed &x) const{
		return x.w<w;
	}
};
vector<ed>G[300100];
priority_queue<ed>Q;
vector<int>g[301000];
bool vis[300100];
int ru[301000],sta[301000],sz[301000],top,tmd[301000];
int main(){
	scanf("%d%d%d",&n,&m,&s);
	for(int u,v,i=1;i<=m;i++){
		ll w;scanf("%d%d%lld",&u,&v,&w);
		G[u].push_back((ed){v,w});
		G[v].push_back((ed){u,w});
	}
    memset(dis,0x7f,sizeof(dis));
    dis[s]=0;Q.push((ed){s,0});

    while(!Q.empty()){
		ed uu=Q.top();Q.pop();
		int u=uu.v;if(vis[u])continue;vis[u]=1;
		for(ed t:G[u])if(dis[t.v]>dis[u]+t.w){
			dis[t.v]=dis[u]+t.w;
			Q.push((ed){t.v,dis[t.v]});
		}
	}
    for(int i=1;i<=n;i++)for(ed t:G[i])if(dis[i]+t.w==dis[t.v])g[i].push_back(t.v),ru[t.v]++;
	for(int i=1;i<=n;i++)tmd[i]=i;
	sta[++top]=s;
    int ans=0;
	while(top){
		int u=sta[top--],id;
		if(tmd[u]!=-1&&tmd[u]!=s)id=tmd[u];
		else id=u;
		if(id!=s)sz[id]++,ans=max(ans,sz[id]);
		for(int v:g[u]){
			if(tmd[v]==v)tmd[v]=id;
			else if(tmd[v]!=id)tmd[v]=-1;
			if(!(--ru[v]))sta[++top]=v;
		}
	}

   return printf("%d",ans),0;



	
}/*1694389898.3737822*/