【五校联考6day2】san

这题就是枚举起点，然后跑个spfa，最后用dfs来统计答案即可。
上标：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node{int v,fr,l;}e[20010];
int n,m,f[20010],tail[2010],cnt=0;
int aw[2010],b[2010],d[2010];
bool bz[2010];

inline int read()
{
	int x=0; char c=getchar();
	while (c<'0' || c>'9') c=getchar();
	while (c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x;
}

inline void add(int u,int v,int l) {e[++cnt]=(node){v,tail[u],l}; tail[u]=cnt;}

void dfs(int x,int fa)
{
	b[x]=(d[x] & 1);
	for (int p=tail[x],v;p;p=e[p].fr)
		if (d[x]+e[p].l==d[v=e[p].v])
			dfs(v,x),b[x]+=b[v];
	aw[x]+=b[x];
}

void spfa(int x)
{
	memset(d,10,sizeof(d));
	int l=0,r=1;f[1]=x,d[x]=0;
	while (l++<r)
	{
		for (int p=tail[f[l]],v;p;p=e[p].fr)
			if (d[f[l]]+e[p].l<d[v=e[p].v])
			{
				d[v]=d[f[l]]+e[p].l;
				if (!bz[v]) f[++r]=v,bz[v]=1;
			}
		bz[f[l]]=0;
	}
	dfs(x,0);
}

int main()
{
	freopen("san.in","r",stdin);
	freopen("san.out","w",stdout);
	n=read(),m=read();
	for (int i=1,u,v,l;i<=m;i++)
		u=read(),v=read(),l=read(),add(u,v,l),add(v,u,l);
	for (int i=1;i<=n;i++) spfa(i);
	for (int i=1;i<=n;i++) printf("%d
",aw[i]);
	return 0;
}