- 给定一张(n)个点(m)条边的图和一个起点(s)，求删去一个点最多能改变(s)到多少个点的最短路。
- (nle2 imes10^5,mle3 imes10^5)
最短路图
考虑我们建出原图的最短路图。
即，设(dis_x)为(s)到(x)的最短路，则对于一条边((x,y,v))，如果满足(dis_x+v=dis_y)，则连一条(x ightarrow y)的有向边。
由于(dis_x+v=dis_y)的必要条件是(dis_x<dis_y)，所以这是一张(DAG)。
显然，这张图上从(s)出发的每一条路径与原图中从(s)出发的每一条最短路一一对应。
因此这道题要求的其实就是最短路图上最大的支配集大小，直接建出支配树就好了（当然也可以不用支配树，下面会介绍另一种做法）。
拓扑做法
虽然很容易想到无脑去建支配树，但为了偷懒参考了一下题解里不用支配树的做法。
注意到我们要求的是最大的支配集大小，因此只要考虑极大支配集，即如果(y)被(x)支配，则选择(x)肯定优于选择(y)。
对于一个入度为(1)且入点不为(s)的点，它显然被它的入点支配，因此我们可以直接把它合并给它的入点。
实际上，由于执行了合并操作，只有一个入点就是被支配的充要条件，也就是说如果一个点有多个不同的入点或它的入点就是(s)，则不用把它合并给任何点。
这样一来，最终每一个合成点实际上都对应着一个极大支配集，那么只要求出其中最大的大小即为答案。
代码：(O(m))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 200000
#define M 300000
#define add(x,y,z) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y,e[ee].v=z)
using namespace std;
int n,m,s,ee,lnk[N+5];struct edge {int to,nxt,v;}e[2*M+5];
namespace FastIO
{
#define FS 100000
#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
char oc,FI[FS],*FA=FI,*FB=FI;
Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
}using namespace FastIO;
long long dis[N+5];int IQ[N+5];queue<int> Q;I void SPFA()//最短路
{
RI i,k;for(i=1;i<=n;++i) dis[i]=1e18;dis[s]=0,Q.push(s);
W(!Q.empty()) for(i=lnk[k=Q.front()],Q.pop(),IQ[k]=0;i;i=e[i].nxt)
dis[k]+e[i].v<dis[e[i].to]&&(dis[e[i].to]=dis[k]+e[i].v,!IQ[e[i].to]&&(Q.push(e[i].to),IQ[e[i].to]=1));
}
int q[N+5],fa[N+5],sz[N+5],deg[N+5];I void Topo()//最短路图上拓扑
{
RI i,k,H,T;for(k=1;k<=n;++k) for(i=lnk[k];i;i=e[i].nxt) dis[k]+e[i].v==dis[e[i].to]&&++deg[e[i].to];//初始化度数
q[H=T=1]=s;W(H<=T) for(i=lnk[k=q[H++]];i;i=e[i].nxt) dis[k]+e[i].v==dis[e[i].to]&&//初始只有s入队
(fa[e[i].to]=k==s||fa[e[i].to]&&fa[e[i].to]^fa[k]?e[i].to:fa[k],!--deg[e[i].to]&&(++sz[fa[q[++T]=e[i].to]]));//只有一个入点且不为s则合并
RI t=0;for(i=1;i<=n;++i) t=max(t,sz[i]);printf("%d
",t);//最大的支配集大小
}
int main()
{
RI i,x,y,z;for(read(n),read(m),read(s),i=1;i<=m;++i) read(x),read(y),read(z),add(x,y,z),add(y,x,z);
return SPFA(),Topo(),0;
}