题意
建出最短路图（DAG）之后就跟这题一样了。
code:
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define mkp make_pair
#define fir first
#define sec second
const int maxn=2*1e5+10;
const int maxm=3*1e5+10;
int n,m,st,ans,cnt;
int ex[maxm],ey[maxm],ew[maxm],head[maxn],dis[maxn],size[maxn],dep[maxn],deg[maxn];
int f[maxn][20];
bool vis[maxn];
struct edge{int to,nxt;}e[maxn];
struct Edge{int to,dis;};
vector<Edge>E[maxn],e1[maxn],e2[maxn];
inline int read()
{
char c=getchar();int res=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();
return res*f;
}
inline void add(int u,int v)
{
e[++cnt].nxt=head[u];
head[u]=cnt;
e[cnt].to=v;
}
inline int lca(int x,int y)
{
if(dep[x]>dep[y])swap(x,y);
for(int i=18;~i;i--)if(dep[f[y][i]]>=dep[x])y=f[y][i];
if(x==y)return x;
for(int i=18;~i;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
return f[x][0];
}
inline void dijstra()
{
memset(dis,0x3f,sizeof(dis));
priority_queue<pii>q;
dis[st]=0;q.push(mkp(0,st));
while(!q.empty())
{
int x=q.top().sec;q.pop();
if(vis[x])continue;
vis[x]=1;
for(unsigned int i=0;i<E[x].size();i++)
{
int y=E[x][i].to;
if(dis[y]>dis[x]+E[x][i].dis)
{
dis[y]=dis[x]+E[x][i].dis;
q.push(mkp(-dis[y],y));
}
}
}
}
inline void topsort()
{
queue<int>q;
q.push(st);dep[st]=1;
while(!q.empty())
{
int x=q.front();q.pop();
for(unsigned int i=0;i<e1[x].size();i++)
{
int y=e1[x][i].to;
deg[y]--;
if(!deg[y])
{
int z=0;
for(unsigned int j=0;j<e2[y].size();j++)z=!z?e2[y][j].to:lca(z,e2[y][j].to);
add(z,y);f[y][0]=z;dep[y]=dep[z]+1;
for(int j=1;j<=18;j++)f[y][j]=f[f[y][j-1]][j-1];
q.push(y);
}
}
}
}
void dfs(int x)
{
size[x]=1;
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
dfs(y);size[x]+=size[y];
}
}
signed main()
{
n=read(),m=read(),st=read();
for(int i=1;i<=m;i++)
{
ex[i]=read(),ey[i]=read(),ew[i]=read();
E[ex[i]].push_back((Edge){ey[i],ew[i]});
E[ey[i]].push_back((Edge){ex[i],ew[i]});
}
dijstra();
for(int i=1;i<=m;i++)
{
if(dis[ex[i]]==dis[ey[i]]+ew[i])swap(ex[i],ey[i]);
if(dis[ey[i]]==dis[ex[i]]+ew[i])e1[ex[i]].push_back((Edge){ey[i],1}),e2[ey[i]].push_back((Edge){ex[i],1}),deg[ey[i]]++;
}
topsort();dfs(st);
for(int i=1;i<=n;i++)if(i!=st)ans=max(ans,size[i]);
printf("%lld",ans);
return 0;
}