题目链接
转载自https://www.cnblogs.com/wally/archive/2013/05/28/3103437.html（侵转删）
题目：
Invade the Mars
Time Limit: 5000/2000 MS (Java/Others)
Memory Limit: 365768/165536 K (Java/Others)
Total Submission(s): 3169
Accepted Submission(s): 902
Problem Description
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
5
Hint
The Map is like this:
We can follow these ways to achieve the fastest speed:
1->2->3,1->2->5,1->4->6.
思路：题目意思很简单，就是说如果没有攻占保护x的城市，就不能攻占,我们可以用pro[x]记录保护x的所有城市被攻占的最早时间，那么能到x的最短时间为pro[x]和到达x的最短路中的较大者 .dij入队过程中只把In[x]（没有被包含的城市）入队 对于出队的x,它的最短时间已经确定,表示已经被占领,它所保护的城市的保护度减 1,一旦某个被保护的城市的保护度为零且已经到底（未占领，d[x]!=inf），就可以确定到达它的 最短时间（为max(pro[x],dist[x])）,它也就到了入队的时机。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef pair<LL,int>Pair;
#define inf (1ll)<<55
#define MAXN 3333
struct Node {
int v,w;
};
int In[MAXN];
LL dist[MAXN],pro[MAXN];
bool mark[MAXN];
vector<Node>Map[MAXN];
vector<int>vet[MAXN];
int n,m;
void Dijkstra(){
for(int i=1;i<=n;i++){ dist[i]=inf;pro[i]=0; }
dist[1]=0;
memset(mark,false,sizeof(mark));
priority_queue<Pair,vector<Pair>,greater<Pair> >Q;
Q.push(make_pair(dist[1],1));
while(!Q.empty()){
Pair pp=Q.top();
Q.pop();
int u=pp.second;
if(mark[u])continue;
mark[u]=true;
for(int i=0;i<vet[u].size();i++){
int v=vet[u][i];
In[v]--;
pro[v]=max(pro[v],dist[u]);
if(dist[v]!=inf&&In[v]==0){
dist[v]=max(dist[v],pro[v]);
Q.push(make_pair(dist[v],v));
}
}
for(int i=0;i<Map[u].size();i++){
int v=Map[u][i].v;
int w=Map[u][i].w;
if(dist[v]>dist[u]+w){
dist[v]=max(dist[u]+w,pro[v]);
if(In[v]==0){ Q.push(make_pair(dist[v],v)); }
}
}
}
}
int main() {
int _case,u,v,w,x;
scanf("%d",&_case);
while(_case--) {
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++) {
Map[i].clear();
vet[i].clear();
}
while(m--) {
scanf("%d%d%d",&u,&v,&w);
Node p;
p.v=v,p.w=w;
Map[u].push_back(p);
}
for(int i=1; i<=n; i++) {
scanf("%d",&In[i]);
for(int j=1; j<=In[i]; j++) {
scanf("%d",&x);
vet[x].push_back(i);
}
}
Dijkstra();
printf("%I64d\n",dist[n]);
}
return 0;
}