求出最长路.....
1 #include <iostream> 2 #include <vector> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 #include <cmath> 7 #include <map> 8 #include <set> 9 #include <string> 10 #include <queue> 11 using namespace std; 12 #define pb(x) push_back(x) 13 #define ll long long 14 #define mk(x, y) make_pair(x, y) 15 #define lson l, m, rt<<1 16 #define mem(a) memset(a, 0, sizeof(a)) 17 #define rson m+1, r, rt<<1|1 18 #define mem1(a) memset(a, -1, sizeof(a)) 19 #define mem2(a) memset(a, 0x3f, sizeof(a)) 20 #define rep(i, a, n) for(int i = a; i<n; i++) 21 #define ull unsigned long long 22 typedef pair<int, int> pll; 23 const double PI = acos(-1.0); 24 const double eps = 1e-8; 25 const int mod = 1e9+7; 26 const int inf = 1061109567; 27 const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; 28 const int maxn = 1e6+5; 29 int head[maxn], dis[10005], num, val[10005]; 30 struct node 31 { 32 int to, nextt, c; 33 }e[maxn]; 34 void add(int u, int v, int c) { 35 e[num].to = v; 36 e[num].nextt = head[u]; 37 e[num].c = c; 38 head[u] = num++; 39 } 40 void init() { 41 mem1(dis); 42 mem1(head); 43 num = 0; 44 } 45 int dfs(int u) { 46 if(~dis[u]) 47 return dis[u]; 48 int ret = val[u], ans = 0; 49 for(int i = head[u]; ~i; i = e[i].nextt) { 50 int v = e[i].to; 51 ans = max(ans, dfs(v)); 52 } 53 return dis[u] = ans+ret; 54 } 55 int main() 56 { 57 int n, x, y; 58 while(cin>>n) { 59 init(); 60 for(int i = 1; i<=n; i++) { 61 scanf("%d", &val[i]); 62 scanf("%d", &x); 63 while(x--) { 64 scanf("%d", &y); 65 add(y, i, val[i]); 66 } 67 } 68 for(int i = 1; i<=n; i++) { 69 if(dis[i]==-1) { 70 dis[i] = dfs(i); 71 } 72 } 73 int ans = 0; 74 for(int i = 1; i<=n; i++) { 75 ans = max(ans, dis[i]); 76 } 77 printf("%d ", ans); 78 } 79 return 0; 80 }