记录编号	157636	评测结果	AAAA
题目名称	服务器储存信息问题	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.151 s
提交时间	2015-04-09 17:52:54	内存使用	5.75 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int INF=1e9;
int ans,i,p,zj1,zj2,zj3,n,m;
int rank[30010],mindis[11][30010],dis[30010];
bool vis[30010];

int to[300100],ne[300100],w[300100],head[30010],sj=1;
inline void addedge(int u,int v,int c)
{
	to[++sj]=v,ne[sj]=head[u],head[u]=sj,w[sj]=c;
	to[++sj]=u,ne[sj]=head[v],head[v]=sj,w[sj]=c;
}
int TO[30010],HEAD[15],NE[30010],SJ=0;
inline void ADDEDGE(int u,int v){TO[++SJ]=v,NE[SJ]=HEAD[u],HEAD[u]=SJ;}


int que[31000],qhead=1,qtail=0,qnum=0;bool flag[30010];
inline void PUSH(int x)
{if(++qtail==31000)qtail=1;que[qtail]=x,qnum++,flag[x]=1;}
inline int GET()
{int x=que[qhead];flag[x]=0,qnum--;if(++qhead==31000)qhead=1;return x;}

inline void spfa1()
{
	memset(mindis[i],0x3f,sizeof(mindis[i]));
	for(p=HEAD[i];p;p=NE[p])PUSH(TO[p]),mindis[i][TO[p]]=0;
	while(qnum)for(p=head[zj1=GET()];p;p=ne[p])
	if(mindis[i][zj1]+w[p]<mindis[i][to[p]])
	{
		mindis[i][to[p]]=mindis[i][zj1]+w[p];
		if(!flag[to[p]])PUSH(to[p]);
	}
}

inline void spfa2(){
	memset(dis,0x3f,sizeof(dis));
	memset(vis,false,sizeof(vis));
	dis[i]=0;PUSH(i);
	while(qnum)
	{
		if(!vis[zj1=GET()])ans++,vis[zj1]=1;
		for(p=head[zj1];p;p=ne[p])
		if(dis[to[p]]>w[p]+dis[zj1])
		{
			dis[to[p]]=w[p]+dis[zj1];
			//逆向考虑，i节点在目标节点可允许范围内 
			if(!flag[to[p]]&&mindis[rank[i]+1][to[p]]>dis[to[p]]) 
			PUSH(to[p]);
		}
	}
}

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",&rank[i]);
		ADDEDGE(rank[i],i);
	}
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&zj1,&zj2,&zj3);
		addedge(zj1,zj2,zj3);
	}
	for(i=1;i<=10;i++)spfa1();
	for(i=9;i;i--)for(p=1;p<=n;p++)
	if(mindis[i][p]>mindis[i+1][p])
	mindis[i][p]=mindis[i+1][p];
	for(i=1;i<=n;i++)spfa2();
	printf("%d\n",ans);
	return 0;
}