题解 P5340 【[TJOI2019]大中锋的游乐场】

· · 题解

又是一道分层图最短路的练手题。

设 f_{i,j} 表示当前在 i 号点，汉堡比可乐多 j 次时的最短路。

别忘了起点也是要吃汉堡/喝可乐的。

// Problem : P5340 [TJOI2019]大中锋的游乐场
// Contest : Luogu Online Judge
// URL : https://www.luogu.com.cn/problem/P5340
// Author : StudyingFather
// Site : https://studyingfather.com
// Memory Limit : 125 MB
// Time Limit : 1000 ms
// Powered by CP Editor (https://github.com/cpeditor/cp-editor)

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
struct edge
{
 int v,w,next;
}e[200005];
struct node
{
 int u,t,w;
 bool operator<(const node&a)const
 {
  return w>a.w;
 }
};
priority_queue<node> q;
int head[10005],dis[10005][25],vis[10005][25],cnt;
int a[10005];
void addedge(int u,int v,int w)
{
 e[++cnt].v=v;
 e[cnt].w=w;
 e[cnt].next=head[u];
 head[u]=cnt;
}
int main()
{
 int T;
 cin>>T;
 while(T--)
 {
  cnt=0;
  memset(head,0,sizeof(head));
  memset(dis,63,sizeof(dis));
  memset(vis,0,sizeof(vis));
  int n,m,k,s,t;
  cin>>n>>m>>k;
  for(int i=1;i<=n;i++)
  {
   cin>>a[i];
   if(a[i]==2)a[i]=-1;
  }
  for(int i=1;i<=m;i++)
  {
   int u,v,w;
   cin>>u>>v>>w;
   addedge(u,v,w);
   addedge(v,u,w);
  }
  cin>>s>>t;
  dis[s][k+a[s]]=0;//注意初始状态
  q.push({s,k+a[s],0});
  while(!q.empty())
  {
   int u=q.top().u,t=q.top().t;
   q.pop();
   if(vis[u][t])continue;
   vis[u][t]=1;
   for(int i=head[u];i;i=e[i].next)
   {
    int v=e[i].v,nt=t+a[v];
    if(nt<=2*k&&nt>=0&&dis[v][nt]>dis[u][t]+e[i].w)
    {
     dis[v][nt]=dis[u][t]+e[i].w;
     q.push({v,nt,dis[v][nt]});
    }
   }
  }
  int ans=INF;
  for(int i=0;i<=2*k;i++)
   ans=min(ans,dis[t][i]);
  if(ans==INF)cout<<-1<<endl;
  else cout<<ans<<endl;
 }
 return 0;
}