2015
04-13

# Invade the Mars

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.

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.

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.

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

5

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



DIJ维护两个量，一个是保护该城市的城市所有被摧毁的最大时间，还有就是能到达该城市的最小距离，两者取最大值

#include <cstdio>
#include <cstring>
const int MAXN = 3000 + 123;
const int MAXM = 70000 + 1234;
const int MAXMM = 3000 * 1510;
struct EDGE
{
int v, next, val;
}edge[MAXM];
struct EDGE2
{
int v, next;
}pro[MAXMM];
int head[MAXN];
int first[MAXN];
int rest[MAXN];
int d[MAXN];
int f[MAXN];
bool vis[MAXN];
int cnt;
int num;
int n, m;
void addedge(int u, int v, int val)
{
edge[cnt].v = v;
edge[cnt].val = val;
edge[cnt].next = head[u];
head[u] = cnt++;
}
void addedge2(int u, int v)
{
rest[v]++;
pro[num].v = v;
pro[num].next = first[u];
first[u] = num++;
}
void init()
{
cnt = 0;
num = 0;
memset(head, -1, sizeof(head));
memset(first, -1, sizeof(first));
memset(rest, 0, sizeof(rest));
memset(vis, 0, sizeof(vis));
memset(f, 0, sizeof(f));
memset(d, 60, sizeof(d));
}
void dij()
{
d[1] = 0;
f[1] = 0;
int minp = 1;
for(int k= 1; k < n ; k++)
{
vis[minp] = 1;
for(int p = first[minp]; p != -1; p = pro[p].next)
{
//printf("i=%d\n",i);
rest[pro[p].v] --;
if(d[minp] > f[pro[p].v])  f[pro[p].v] = d[minp];
}

for(int p = head[minp]; p != -1; p = edge[p].next)
{
int j = edge[p].v;
if(edge[p].val + d[minp] < d[j])
{
d[j] = edge[p].val + d[minp];
//d[j] = f[j] > d[j] ? f[j] : d[j];
}
}

for(int j = 1; j <= n; j++)  //wa 了 n  次
{
d[j] = f[j] > d[j] ? f[j] : d[j];
}

//for(int i = 1; i <= n; i++)  printf("d[%d]= %I64d\n", i, d[i]);
minp = 0;
for(int j = 2; j <= n; j++)
if(rest[j] == 0 && !vis[j])
{
if (d[j] < d[minp]) minp=j;
}
}
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d%d", &n, &m);
init();
int a, b, c;
for(int i = 1; i <= m; i++)
{
scanf("%d%d%d",&a, &b, &c);
addedge(a, b, c);
}

int x;
for(int i = 1; i <= n; i++)
{
scanf("%d", &x);
for(int j = 1; j <= x; j++)
{
scanf("%d", &a);
addedge2(a,i);
}
}
dij();
printf("%d\n", d[n]);
}
return 0;
}


,
1. 第二种想法，我想来好久，为啥需要一个newhead，发现是把最后一个节点一直返回到嘴上面这层函数。厉害，这道题之前没样子想过。

2. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同，其树的前、中、后序遍历是相同的，但在此处不能使用中序遍历，因为，中序遍历的结果就是排序的结果。经在九度测试，运行时间90ms，比楼主的要快。