带限制的dijkstra，由题意得，每个城市的实际最早进入时间=max（最短路，所有结界点城市的最大最短路）
考虑实现，我们可以记录每个点的入度或是哪个城市保护哪个城市，在维护到某点时判断是否可以进入。若不能进入则continue，能则判断进入该城市后可以解锁哪些新的城市，再将新城市更新压入队列。不同的操作很多，怎么写都行。
时间复杂度O(nlogn)
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#define M 70010
#include<queue>
#define N 3010
using namespace std;
struct node
{
int id;
int d;
bool operator < (const node &rhs) const
{
return rhs.d<d;
}
};
priority_queue<node> q;
int n,m,head[N],to[M],e,len[M],Next[M];
void buid(int u,int v,int l)
{
Next[++e]=head[u];head[u]=e;
to[e]=v;len[e]=l;
}
int s[N][N],vis[N];
int d1[N],d2[N],d[N];
void dj()
{
d1[1]=0;
q.push((node){1,max(d1[1],d2[1])});
while(!q.empty())
{
node top=q.top();q.pop();
if(vis[top.id]) continue;
if(top.d!=max(d1[top.id],d2[top.id])) continue;
for(int i=head[top.id];i;i=Next[i])
{
int j=to[i];
if(d1[j]>top.d+len[i])
{
d1[j]=top.d+len[i];
if(!d[j]) q.push((node){j,max(d1[j],d2[j])});
}
}
for(int i=1;i<=s[top.id][0];++i)
{
d[s[top.id][i]]--;
if(!d[s[top.id][i]])
{
d2[s[top.id][i]]=top.d;
q.push((node){s[top.id][i],max(d1[s[top.id][i]],d2[s[top.id][i]])});
}
}
}
printf("%d",max(d1[n],d2[n]));
}
int main()
{
scanf("%d%d",&n,&m);
memset(d1,20,sizeof(d1));
for(int i=1;i<=m;++i)
{
int u,v,l;scanf("%d%d%d",&u,&v,&l);
buid(u,v,l);
}
for(int i=1;i<=n;++i)
{
scanf("%d",&d[i]);
for(int j=1;j<=d[i];++j)
{
int it;scanf("%d",&it);
s[it][++s[it][0]]=i;
}
}
dj();
return 0;
}