Description：

给一张有向带权图，有一些点会被其他一些点保护，被保护的点不能通过，每个机器人可以沿边移动并摧毁节点，问从一号节点出发派出无限个机器人最早什么时候可以摧毁 $n$ 号节点。

$1\le n \le 3000$

Solution：

做法是最短路，记 $d1[k]$ 表示 $k$ 节点最早什么时候能有机器人到达， $d2[k]$ 表示 $k$ 节点最早什么时候解除封锁，第一个转移和普通最短路一样，第二个转移就是每次 $--ind[e[i].to]$ ，当 $ind[e[i].to]==0$ 时把 $d2[e[i].to]$ 赋为 $d1[k]$ ，转移的时候分别转移这两个部分，但只有这两部分都已经求得最短路时才能被加入队列，所以必须保证第一次被求出时就是最短路，而这题又没有负边权，所以可以用 $dijkstra$ ，每次用 $\max(d1[k],d2[k])$ 来转移，因为这是实际到达的时间。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<vector> 

#include<cstring>

using namespace std;

int n,m;

#define MAXN 3010

#define MAXM 70010

#define INF 0x3f3f3f3f3f3f3f3f

struct edge

{

	int to,nxt,v;

}e[MAXM];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int c)

{

	++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

vector<int> g[MAXN];

typedef long long ll;

ll d1[MAXN],d2[MAXN];

bool v[MAXN];

int ind[MAXN] = {0};

bool arrive[MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	int a,b,c;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&a,&b,&c);

		add(a,b,c);

	}

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&ind[i]);

		for(int k = 1;k <= ind[i];++k)

		{

			scanf("%d",&b);

			g[b].push_back(i);

		}

	}

	memset(v,false,sizeof(v));

	memset(d1,0x3f,sizeof(d1));

	memset(d2,0x3f,sizeof(d2));

	memset(arrive,0,sizeof(arrive));

	for(int i = 1;i <= n;++i)

	{

		if(ind[i] == 0)d2[i] = 0;

	}

	priority_queue< pair<ll,int> > q;

	q.push(make_pair(0ll,1));

	d1[1] = 0;arrive[1] = true;

	while(!q.empty())

	{

		int k = q.top().second;q.pop();

		if(v[k])continue;

		v[k] = true;

		ll dis = max(d1[k],d2[k]);

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(d1[e[i].to] > dis + e[i].v)

			{

				d1[e[i].to] = dis + e[i].v;

				arrive[e[i].to] = true;

				if(ind[e[i].to] == 0)

				{

					q.push(make_pair(-max(d1[e[i].to],d2[e[i].to]),e[i].to));

				}

			}

		}

		for(int i = 0;i < g[k].size();++i)

		{

			--ind[g[k][i]];

			if(ind[g[k][i]] == 0)

			{

				d2[g[k][i]] = dis;

				if(arrive[g[k][i]])

				{

					q.push(make_pair(-max(d1[g[k][i]],d2[g[k][i]]),g[k][i]));

				}

			}

		}

	}

	cout << max(d1[n],d2[n]) << endl;	

	return 0;

}