记录编号	56221	评测结果	AAAA
题目名称	服务器储存信息问题	最终得分	100
用户昵称	feng	是否通过	通过
代码语言	C++	运行时间	0.184 s
提交时间	2013-03-27 17:10:32	内存使用	21.86 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
struct node{
	int nex;
}a[30001];
struct edge{
	int nex,v,y;
}e[400001];
int n,m,ans,p;
bool f[30001];
int vis[30001];
int dis[20][30001];
int queue[3000001];
int r[30001];
void add(int x,int y,int v){
	p++;
	e[p].nex=a[x].nex;
	a[x].nex=p;
	e[p].v=v;
	e[p].y=y;
}
void init(){
	freopen("servers.in","r",stdin);
	freopen("servers.out","w",stdout);
	scanf("%d%d",&n,&m);
	int x,y,v;
	for (int i=1;i<=n;i++)
		scanf("%d",&r[i]);
	for (int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&v);
		add(x,y,v);
		add(y,x,v);
	}
	for (int i=1;i<=n;i++){
		add(r[i]+n,i,0);
		add(i,r[i]+n,0);
	}
}
int i;
void spfa1(){
	memset(f,false,sizeof(f));
	int head=0,tail;
	queue[tail=1]=i+n;
	for (int j=1;j<=n;j++)
		dis[i][j]=1000000000;
	while (head<tail){
		int s=queue[++head];
		f[s]=false;
		int t=a[s].nex;
		while (t){
			if (dis[i][s]+e[t].v<dis[i][e[t].y]){
				dis[i][e[t].y]=dis[i][s]+e[t].v;
				if (!f[e[t].y]){
					queue[++tail]=e[t].y;
					f[e[t].y]=true;
				}
			}
			t=e[t].nex;
		}
	}
}
bool tj[30001];
void spfa2(){
	memset(f,false,sizeof(f));
	memset(vis,-1,sizeof(vis));
	memset(tj,false,sizeof(tj));
	int head=0,tail;
	queue[tail=1]=i;
	vis[i]=0;
	while (head<tail){
		int s=queue[++head];
		int t=a[s].nex;
		f[s]=false;
		if (!tj[s]) ans++;
		tj[s]=true;
		while (t){
			if (e[t].y<=n){
				if (vis[e[t].y]<0 || vis[e[t].y]>e[t].v+vis[s]){
					vis[e[t].y]=e[t].v+vis[s];
					if (!f[e[t].y]){
						int j;
						for (j=r[i]+1;j<=10;j++)
							if (dis[j][e[t].y]<=vis[e[t].y]) break;
						if (j==11){
							queue[++tail]=e[t].y;
							f[e[t].y]=true;
						}
					}
				}
			}
			t=e[t].nex;
		}
	}
}
void work(){
	for (i=1;i<=10;i++)
		spfa1();/*
	for (int i=1;i<=10;i++){
		for (int j=1;j<=n;j++)
			printf("%d ",dis[i][j]);
		printf("\n");
	}*/
	for (i=1;i<=n;i++){
		//printf("%d\n",ans);
		spfa2();
	}
	printf("%d",ans);
}
int main()
{
	init();
	work();
	return 0;
}