1 /* 2         题意：n个任务，有某些任务要在一些任务之前完成才能开始做！ 3                     第k个任务的约束只能是1...k-1个任务！问最终需要最少的时间完成全部的                      4                     任务！     5        思路：第i个任务要在第j个任务之前做，就在i，j之间建立一条有向边！ 6                    如果第i个任务之前没有任务，那么就是0和i建立一条有向边！ 7                    最后求一条0到所有节点距离的最大值！不一定是最后一个任务完成的 8                    时间是最长的时间....... 9 */10 #include<iostream>11 #include<cstring>12 #include<cstdio>13 #include<algorithm>14 #include<vector> 15 #include<queue>16 #define N 10005 17 using namespace std;18 19 struct Edge{20     int v, w;21     Edge(){}22     23     Edge(int v, int w){24         this->v=v;25         this->w=w;26     }27 }; 28 29 queue<int>q;30 vector<Edge>g[N];31 int d[N];32 int vis[N]; 33 int maxT;34 void spfa(){35     q.push(0);36     vis[0]=1;37     while(!q.empty()){38         int u=q.front();39         q.pop();40         vis[u]=0;41         int len=g[u].size();42         for(int i=0; i<len; ++i){43             int v=g[u][i].v, w=g[u][i].w;44             if(d[v]<d[u]+w){45                 d[v]=d[u]+w;46                 if(maxT<d[v]) maxT=d[v]; 47                 if(!vis[v]){48                     q.push(v);49                     vis[v]=1;50                 }51             }52         }53     }54 }55 int main(){56     int n;57     scanf("%d", &n);58     for(int i=1; i<=n; ++i){59             d[i]=vis[i]=0;60             int tt, m;61             scanf("%d%d", &tt, &m);62             if(m==0) g[0].push_back(Edge(i, tt));63             while(m--){64                 int v;65                 scanf("%d", &v);66                 g[v].push_back(Edge(i, tt));67             } 68     }69     maxT=0;70     spfa();71     printf("%d\n", maxT); 72     return 0;73 }           

 1 /* 2           思路：其实是一个简单的dp题目！ 3 */ 4 #include<iostream> 5 #include<cstring> 6 #include<cstdio> 7 #include<algorithm> 8 #define N 10005 9 using namespace std;10 int dp[N];11 int main(){12     13     int n, maxT=0;14     scanf("%d", &n);15     for(int i=1; i<=n; ++i){16         int w, m;17         scanf("%d%d", &w, &m);18         if(m==0) dp[i]=w;//不仅仅只有1节点没有约束节点19         20         while(m--){21             int v;22             scanf("%d", &v);23             dp[i]=max(dp[i], dp[v]+w);24         }25         if(maxT<dp[i]) maxT=dp[i];26     }27     printf("%d\n", maxT);28     return 0;29 }