比赛 20110318 评测结果 AAAA
题目名称 服务器储存信息问题 最终得分 100
用户昵称 Pom 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-03-18 19:09:36
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

const int MAXN=30050;
const int M=MAXN+10000;

struct edge
{
	int t,c;
	edge *p;
}e[MAXN*11],*v[MAXN];

int n,m,i,j,k,es=-1,dis[11][MAXN],rk[MAXN],Q[MAXN*2],ans,dist[MAXN];
bool iq[MAXN],tj[MAXN];

inline void addedge(int i,int j,int c)
{
	e[++es].t=j; e[es].c=c; e[es].p=v[i]; v[i]=e+es;
	e[++es].t=i; e[es].c=c; e[es].p=v[j]; v[j]=e+es;
}

void spfa1()
{
	int h,t,s;
	h=t=s=1;
	Q[1]=i+n;
	for (j=1;j<=n;j++)
		dis[i][j]=1000000000;
	while (s)
	{
		k=Q[h];
		for (edge *x=v[k];x;x=x->p)
			if (dis[i][x->t]>dis[i][k]+x->c)
			{
				dis[i][x->t]=dis[i][k]+x->c;
				if (!iq[x->t])
				{
					t=(t+1)%M;
					Q[t]=x->t;
					++s;
					iq[x->t]=true;
				}
			}
		iq[k]=false;
		h=(h+1)%M;
		--s;
	}
}

void spfa()
{
	int h,t,s;
	memset(dist,-1,sizeof(dist));
	memset(tj,false,sizeof(tj));
	h=t=s=1;
	Q[1]=i;
	dist[i]=0;
	while (s)
	{
		k=Q[h];
		if (!tj[k]) ans++;
		tj[k]=true;
		for (edge *x=v[k];x;x=x->p)
			if (x->t<=n)
				if (dist[x->t]<0 || dist[x->t]>x->c+dist[k])
				{
					dist[x->t]=x->c+dist[k];
					if (!iq[x->t])
					{
						for (j=rk[i]+1;j<=10;j++)
							if (dis[j][x->t]<=dist[x->t]) break;
						if (j==11)
						{
							t=(t+1)%M;
							Q[t]=x->t;
							++s;
							iq[x->t]=true;
						}
					}
				}
		--s;
		h=(h+1)%M;
		iq[k]=false;
	}
}

int main()
{
	freopen("servers.in","r",stdin);
	freopen("servers.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++)
		scanf("%d",&rk[i]);
	while (m--)
	{
		scanf("%d%d%d",&i,&j,&k);
		addedge(i,j,k);
	}
	for (i=1;i<=n;i++)
		addedge(rk[i]+n,i,0);
	for (i=1;i<=10;i++)
		spfa1();
	for (i=1;i<=n;i++)
		spfa();
	printf("%d\n",ans);
	return 0;
}