P5340 分层图最短路 评测记录

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0;char c;
	c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x;
}
const int N=10004,M=100005,K=12;
int n,m,k,s,t;
bool a[N];//cola
inline int P(int i,int j){return i*n+j+k*n;}
const int MAXN=2*K*N+N,MAXM=4*K*N;
int head[MAXN],to[MAXM],nxt[MAXM],cnt;long long w[MAXM];
inline void add(int a,int b,int c){
	++cnt;
	to[cnt]=b;
	w[cnt]=c;
	nxt[cnt]=head[a];
	head[a]=cnt;
	return;
}
void init(){
	n=read();m=read();k=read();
	for(int i=1;i<=n;++i)
		a[i]=(read()==1);
	memset(head,0,sizeof(head));
	cnt=0;
	for(int i=1,u,v,w;i<=m;++i){
		u=read();v=read();w=read();
		if(a[v])
			for(int i=-k;i<k;++i)
				add(P(i,u),P(i+1,v),w);
		else
			for(int i=k;i>-k;--i)
				add(P(i,u),P(i-1,v),w); 
		if(a[u])
			for(int i=-k;i<k;++i)
				add(P(i,v),P(i+1,u),w);
		else
			for(int i=k;i>-k;--i)
				add(P(i,v),P(i-1,u),w);
	}
	s=read();t=read();
	return;
}
priority_queue<pair<long long,int> > q;
bool vis[MAXN];long long dis[MAXN];int now;
void dijkstra(){
	memset(vis,0,sizeof(vis));memset(dis,0x3f,sizeof(dis));
	q.push(make_pair(dis[(a[s]?P(1,s):P(-1,s))]=0,(a[s]?P(1,s):P(-1,s))));
	while(!q.empty()){
		now=q.top().second;
		q.pop();
		if(vis[now]) continue;
		vis[now]=true;
		for(int i=head[now];i;i=nxt[i])
			if(dis[to[i]] > dis[now]+w[i]){
				dis[to[i]]=dis[now]+w[i];
				q.push(make_pair(-dis[to[i]],to[i]));
			}
	}
	return;
}
int main(){
	int T=read();
	long long ans;
	while(T--){
		init();
		dijkstra();
		ans=dis[P(0,t)];
		for(int i=-k;i<=k;++i)
			ans=min(ans,dis[P(i,t)]);
		printf("%d\n",ans==4557430888798830399?-1:ans);
	}
	return 0;
}