题目大意：给你 n 个任务，编号从 1 ~ n ， 有些任务有前驱任务 ，即前驱任务完成后才能开始该任务，当然，相互之间没有影响的任务可以同时进行，完成每个任务都需要一定的时间，问：完成所有任务需要的最少时间是多少？
解题思路：这个题有点像拓扑排序，因为要开始每个任务前都要完成某些任务，即任务的完成是有先后顺序的，具体方法就是：将每个任务看成一个点，将入度为 0 的点压入队列，然后遍历队列中的顶点（设为 k）的邻接顶点（设为 m ），即 k 是 m 的前驱顶点，更新开始任务 m 所需要的最晚时间 ，同时顶点 m 的入度 减 1 ，当顶点 m 入度为 0 时，把m 压入队列，重复以上步骤，直到队列为空。
请看代码：
#include <iostream>
#include <set>
#include <algorithm>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <stack>
#include <cstring>
#include <map>
#include <vector>
#include <string>
#include <queue>
#include <cmath>
#define eps 1e-7
#define mem(a , b) memset(a , b , sizeof(a) )
using namespace std ;
const int MAXN = 11111 ;
struct Edge
{
int adj ;
int d ;
int next ;
} e[MAXN * 200] ;
int t[MAXN] ; // 存储完成每个任务所需要的时间
int dis[MAXN] ; // 存储开始每个任务的最晚时间
int ind[MAXN] ; // 统计每个顶点的入度
int head[MAXN] ;
int n ;
int ecnt ;
void chu()
{
mem(t , 0) ;
mem(dis , 0) ;
mem(head , -1) ;
mem(ind , 0) ;
mem(vis , 0) ;
ecnt = -1 ;
}
void init()
{
int i ;
for(i = 1 ; i <= n ; i ++)
{
scanf("%d" , &t[i]) ;
int tt ;
scanf("%d" , &tt) ;
ind[i] = tt ;
int j ;
for(j = 0 ; j < tt ; j ++)
{
int a ;
scanf("%d" , &a) ;
ecnt ++ ;
e[ecnt].adj = i ;
e[ecnt].d = t[a] ;
e[ecnt].next = head[a] ;
head[a] = ecnt ;
}
}
}
queue<int> q ;
void spfa()
{
while (!q.empty()) q.pop() ;
int i ;
for(i = 1 ; i <= n ; i ++)
{
if(ind[i] == 0)
q.push(i) ;
}
int tu ;
while(!q.empty())
{
tu = q.front() ;
q.pop() ;
int i ;
for(i = head[tu] ; i != -1 ; i = e[i].next)
{
int td = e[i].d ;
int v = e[i].adj ;
ind[v] -- ;
if(ind[v] == 0) // 当入度为0的时候，就把该点压入队列
{
q.push(v) ;
}
if(dis[tu] + td > dis[v])
{
dis[v] = dis[tu] + td ;
}
}
}
}
void solve()
{
spfa() ;
int i ;
int MAX = 0 ;
for(i = 1 ; i <= n ; i ++)
{
MAX = max(MAX , dis[i] + t[i]) ;
}
printf("%d\n" , MAX) ;
}
int main()
{
while(scanf("%d" , &n) != EOF)
{
chu() ;
init() ;
solve() ;
}
return 0 ;
}