题目大意：美国佬打算入侵火星，火星上有n个城市，有些城市可能受其他城市保护，
如果i城市受j城市保护，那么你必须先攻占j城市才能再攻占i城市，问你攻占城市n的最短时间是多少。
数据解释：
给定t， 表示有t组数据
给定n，m 表示n个点，m条边
接下来m条有向边， a,b,c 表示从a到b，距离为c
接下来n行， 每行第一个整数d，然后接下来是d个整数，x1,x2,...xd， 表示第i个城市受d个城市保护，表示只有城市x1，x2...xd都被攻占，城市i才能被攻占
问从点1到达点n的最短时间（一定是可达的）
重要的一点是，因为是军队，所以可以同时进军多个点。
思路：
如果城市i受其他城市保护， 那么攻占城市i的最短时间是从1-->i和攻占城市i的保护城市 这两个时间中的最大值。
设dist[i] 为 攻占城市i的最短时间， maxn[i] 为攻占所有保护i的城市中时间最长的那个
那么 dist[i] = max(dist[i],maxn[i])
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
#pragma warning(disable:4996)
typedef long long LL;
const int INF = << ;
/* */
struct Edge
{
int to, dist;
bool operator<(const Edge&rhs)const
{
return dist > rhs.dist;
}
};
vector<Edge> g[ + ];
vector<int> pro[ + ];
bool vis[ + ];
int protect[ + ];
int dist[ + ], maxn[ + ], ans[ + ];
void dij(int n)
{
for (int i = ; i <= n; ++i)
{
vis[i] = false;
dist[i] = INF;
maxn[i] = ;
}
dist[] = ;
priority_queue<Edge> q;
Edge cur, tmp;
cur.to = ;
cur.dist = ;
q.push(cur);
while (!q.empty())
{
cur = q.top(); q.pop();
int x = cur.to;
if (vis[x]) continue;
for (int i = ; i < pro[x].size(); ++i)
{
int v = pro[x][i];
maxn[v] = max(maxn[v], dist[x]);//求出到达保护城市v的城市最长的那一个
protect[v]--;
}
vis[x] = true;
for (int i = ; i < g[x].size(); ++i)
{
int v = g[x][i].to;
if (dist[v] > dist[x] + g[x][i].dist)
dist[v] = dist[x] + g[x][i].dist;
}
for (int i = ; i <= n; ++i)
{
if (vis[i]) continue;
dist[i] = max(dist[i], maxn[i]);
if (protect[i] == && dist[i]!=INF)//在点i没有解除约束之前，我们不能让它去更新其它的点
{
tmp.to = i;
tmp.dist = dist[i];
q.push(tmp);
} }
}
} void input(int &x)
{
char ch = getchar();
while (ch > '' || ch < '')
ch = getchar();
x = ;
while (ch >= '' && ch <= '')
{
x = x * + ch - '';
ch = getchar();
}
}
int main()
{
int t, n, m, i, a, b, c;
Edge tmp;
scanf("%d", &t);
while (t--)
{
//scanf("%d%d", &n, &m);
input(n); input(m);
for (i = ; i <= n; ++i)
{
g[i].clear();
pro[i].clear();
}
for (i = ; i < m; ++i)
{
//scanf("%d%d%d", &a, &b, &c);
input(a); input(b); input(c);
tmp.to = b;
tmp.dist = c;
g[a].push_back(tmp);
}
for (int i = ; i <= n; ++i)
{
//scanf("%d", &a);
input(a);
protect[i] = a;
for (int j = ; j < a; ++j)
{
//scanf("%d", &b);
input(b);
pro[b].push_back(i);
}
}
dij(n);
printf("%d\n", dist[n]);
}
return ;
}