模板题居然调一整晚都没调出来。

应该是dijkstra出问题，第八个点总共要十秒左右。代码如下（加调试语句,dij相关）：

bool vis[maxn];
priority_queue<pair<LL,int>,vector<pair<LL,int> >,greater<pair<LL,int> > > Q;
void dijkstra(int s)
{
	ans=0;
	for(int i=1;i<=n;++i) dis[i]=INF;
	dis[s]=0;
	Q.push(make_pair(0,s));
	memset(vis,0,sizeof(vis));
	while(!Q.empty())
	{
		pair<LL,int> cur=Q.top();Q.pop();
		int u=cur.second;
		if(vis[u]) continue;
		vis[u]=true;
		for(int i=head[u],v;i;i=e[i].next)if(!vis[v=e[i].to])
		{
			if(dis[v]>dis[u]+e[i].w){
				dis[v]=dis[u]+e[i].w;
				Q.push(make_pair(dis[v],v));
			}
		}
	}
	for(long long i=1;i<=n;++i){
		ans+=dis[i]<INF?(dis[i]-h[s]+h[i])*i:INF*i;
	}
}

若有好心人回复请@楼主（没法及时看帖），谢谢了。

平均跑三四次（后期两次）dij要16毫秒。