fork(1) download 
  1. #include<cstdio>
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<string>
  5. #include<cstring>
  6. #include<vector>
  7. #include<stack>
  8. #include<queue>
  9. #include<deque>
  10. #include<map>
  11. #include<set>
  12. #include<limits>
  13. #include<climits>
  14. #include<cmath>
  15. #include<functional>
  16. #include<ctime>
  17. #include<cstdlib>
  18. #include<fstream>
  19. #include<typeinfo>
  20.  
  21. using namespace std;
  22.  
  23. typedef long long int ll;
  24. typedef short int i16;
  25. typedef unsigned long long int u64;
  26. typedef unsigned int u32;
  27. typedef unsigned short int u16;
  28. typedef unsigned char u8;
  29.  
  30. FILE *IN = fopen("buffet.in","r");
  31. FILE *OUT = fopen("buffet.out","w");
  32.  
  33. const int N = 1024;
  34.  
  35. int n;
  36.  
  37. ll e;
  38.  
  39. ll min_path[N][N];
  40. queue <int> q;
  41. bool used[N];
  42.  
  43. int grass[N];
  44.  
  45. vector <int> v[N];
  46.  
  47. ll state[N];
  48.  
  49. void input() {
  50.     fscanf(IN, "%d %lld", &n, &e);
  51.  
  52.     int i,d,j,p;
  53.  
  54.     for(i=1;i<=n;i++) {
  55.         fscanf(IN, "%d %d", &grass[i], &d);
  56.  
  57.         for(j=0;j<d;j++) {
  58.             fscanf(IN, "%d", &p);
  59.             v[i].push_back(p);
  60.         }
  61.     }
  62. }
  63.  
  64. void BFS(int starting_node) {
  65.     memset(used,0,sizeof(used));
  66.  
  67.     while(!q.empty()) {
  68.         q.pop();
  69.     }
  70.  
  71.     q.push(starting_node);
  72.     used[starting_node]=true;
  73.  
  74.     min_path[starting_node][starting_node]=0;
  75.  
  76.     int i,curr;
  77.  
  78.     while(!q.empty()) {
  79.         curr=q.front();
  80.         q.pop();
  81.  
  82.         for(i=0;i<v[curr].size();i++) {
  83.             if(!used[v[curr][i]]) {
  84.                 used[v[curr][i]]=true;
  85.                 q.push(v[curr][i]);
  86.                 min_path[starting_node][v[curr][i]]=1+min_path[starting_node][curr];
  87.             }
  88.         }
  89.     }
  90.  
  91.     for(i=1;i<=n;i++) {
  92.         min_path[starting_node][i]*=e;
  93.     }
  94. }
  95.  
  96. void initialize_distances() {
  97.     int i;
  98.  
  99.     for(i=1;i<=n;i++) {
  100.         BFS(i);
  101.     }
  102. }
  103.  
  104. ll recurse(int last_node) {
  105.     if(used[last_node]) {
  106.         return state[last_node];
  107.     }
  108.  
  109.     int next_node;
  110.     ll ans=0;
  111.  
  112.     for(next_node=1;next_node<=n;next_node++) {
  113.         if(grass[next_node]<=grass[last_node] || min_path[last_node][next_node]==0) {
  114.             continue;
  115.         }
  116.  
  117.         ans=max(ans,grass[next_node]-min_path[last_node][next_node]+recurse(next_node));
  118.     }
  119.  
  120.     used[last_node]=true;
  121.     state[last_node]=ans;
  122.  
  123.     return ans;
  124. }
  125.  
  126. void solve() {
  127.     initialize_distances();
  128.  
  129.     memset(used,0,sizeof(used));
  130.  
  131.     ll ans=0;
  132.  
  133.     int i;
  134.  
  135.     for(i=1;i<=n;i++) {
  136.         ans=max(ans,grass[i]+recurse(i));
  137.     }
  138.  
  139.     fprintf(OUT, "%lld\n", ans);
  140. }
  141.  
  142. int main() {
  143.     input();
  144.     solve();
  145.  
  146.     fclose(IN);
  147.     fclose(OUT);
  148.  
  149.     return 0;
  150. }
  151.  
Runtime error #stdin #stdout 0s 11448KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/6pMXeh
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!