Invade the Mars HDU

Invade the Mars HDU"/>

Invade the Mars HDU

问题：

It's now the year 21XX,when the earth will explode soon.The evil U.S. decided to invade the Mars to save their lives. 
But the childlike Marsmen never keeps any army,because war never take place on the Mars.So it's very convenient for the U.S. to act the action. 
Luckily,the Marsmen find out the evil plan before the invadation,so they formed a defense system.The system provides enchantment for some citys,and the enchantment generator for city A maybe set in city B,and to make things worse,both city B and C and more will provide echantment for city A. 
The satelite of U.S. has got the map of the Mars.And they knows that when they enter a city,they can destory all echantment generator in this city at once,and they can enter a city only if they has destoryed all enchantment generator for this city,but troops can stay at the outside of the city and can enter it at the moment its echantment is destoryed.Of course the U.S. army will face no resistance because the Mars keep no army,so troops can invade in many way at the same time. 
Now the U.S. will invade the Mars,give you the map,your task is to calculate the minimium time to enter the capital of the Mars. 

Input

The first line contains an integer T,which is the number of test cases. 
For each testcase: 
The first line contains two integers N and M,1<=N<=3000,1<=M<=70000,the cities is numbered from 1 to N and the U.S. landed on city 1 while the capital of the Mars is city N. 
The next M lines describes M paths on the Mars.Each line contains three integers ai,bi and wi,indicates there is a unidirectional path form ai to bi lasts wi minutes(1<=wi<=10^8). 
The next N lines describes N citys,the 1+M+i line starts with a integer li,followed with li integers, which is the number of cities has a echantment generator protects city i. 
It's guaranteed that the city N will be always reachable.

Output

For each case,print a line with a number indicating the minimium time needed to enter the capital of the Mars.

Sample Input

1
6 6
1 2 1
1 4 3
2 3 1
2 5 2
4 6 2
5 3 2
0
0
0
1 3
0
2 3 5

Sample Output

5Hint
The Map is like this:
We can follow these ways to achieve the fastest speed:
1->2->3,1->2->5,1->4->6.

题意：题意看了好久，意思就是美国要从 1 攻打火星中心N（就是求从1到N的最短距离），但是会给一些 A 城市被 B 城市保护，要想攻打A 城市就必须先攻打 B 城市。

思路：用num[i]标记第i个城市被保护的数目，只有当该点被保护的数目为0时，才能入S集合，从而优化到其他点的时间。当前进入S集合的城市，遍历它所保护的城市，num[i]减一，记录下被保护的城市解除保护所需的最长时间。说的有点绕，看代码会比较清楚。

代码：

#include<stdio.h>
#include<string.h>
#include<vector>
#include<iostream>
#define N 70005
#include<algorithm>
using namespace std;
int book[3005];//标记这个城市是否遍历过
int root[3005];//例root[i]表示起点到i城市的最远距离，i是被保护的城市。
int num[3005];//记录城市i被多少个城市保护
int e[3005][3005];//两城市之间的最短距离
int dis[3005];//起点到i之间的最短距离
vector<int>v[3005];//例如v[u][i],表示u城市保护i城市
int main()
{int t;scanf("%d",&t);while(t--){int n,m,a,b,c,h;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)//容器清空v[i].clear();memset(root,0,sizeof(root));memset(book,0,sizeof(book));memset(e,0x3f3f3f3f,sizeof(e));memset(dis,0x3f3f3f3f,sizeof(dis));memset(num,0,sizeof(num));for(int i=1; i<=m; i++){scanf("%d%d%d",&a,&b,&c);e[a][b]=min(e[a][b],c);}for(int i=1; i<=n; i++){scanf("%d",&num[i]);for(int j=1; j<=num[i]; j++){scanf("%d",&h);v[h].push_back(i);}}dis[1]=0;for(int i=1; i<=n; i++){int minn=0x3f3f3f3f,u;//u是保护的城市for(int j=1; j<=n; j++){dis[j]=max(dis[j],root[j]);//每遍历一个点都要更新一下if(dis[j]<minn&&book[j]==0&&num[j]==0){u=j;minn=dis[j];}}if(minn==0x3f3f3f3f)break;book[u]=1;for(int j=0; j<v[u].size(); j++){int k=v[u][j];//k是被保护的城市num[k]--;root[k]=max(dis[u],root[k]);//选择最大的时间}v[u].clear();//用过之后要清空for(int j=1; j<=n; j++)if(dis[j]>dis[u]+e[u][j])dis[j]=dis[u]+e[u][j];}printf("%d\n",dis[n]);}return 0;
}