fork(1) download 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <vector>
  4. using namespace std;
  5.  
  6.  
  7. const int T = 5001, N = 101;
  8. int maxMoney, startNode, nodes, edges, avTime, win[N], mat[T][N][N];
  9. vector<vector<pair<int, int> > > adjacent;
  10.  
  11.  
  12. void parse_input()
  13. {
  14.     cin >> nodes >> edges >> startNode >> avTime;
  15.     for (int i = 1; i <= nodes; ++i) cin >> win[i]; // money gain for node i
  16.     adjacent.resize(nodes + 1);
  17.     for (int i = 0; i < edges; ++i) {
  18.         int t, x, y;
  19.         cin >> t >> x >> y; // t time between x and y
  20.         adjacent[x].push_back(make_pair(y, t));
  21.         adjacent[y].push_back(make_pair(x, t));
  22.     }
  23. }
  24.  
  25.  
  26. void solve()
  27. {
  28.     /** O(TN^2) */
  29.     maxMoney = win[startNode]; // atribuim maximului castigul de start
  30.     mat[0][startNode][0] = maxMoney; // la momentul de timp t=0 initializam nodul de start
  31.     mat[0][startNode][startNode] = 1; // marcam ca este vizitat in lantul curent
  32.     for (int i = 0; i < avTime; ++i) { // pentru fiecare moment de timp
  33.         for (int j = 1; j <= nodes; ++j) { // luam fiecare nod
  34.             if (mat[i][j][0]) { // si daca s-a putut ajunge in el (avand suma strict pozitiva)
  35.                 for (int k = 0; k < adjacent[j].size(); ++k) { // luam fiecare vecin al lui
  36.                     int tmpTime = i + adjacent[j][k].second; // aflam noul timp pentru vizita vecinului
  37.                     int tmpMoney = mat[i][j][0]; // clonam suma de la care pornim vizita
  38.                     if (!mat[i][j][adjacent[j][k].first]) { // daca nu a mai fost vizitat acel vecin
  39.                         tmpMoney += win[adjacent[j][k].first]; // actualizam suma
  40.                     } // apoi daca vizita intra in timp si obtinem o suma mai buna de bani
  41.                     if (tmpTime <= avTime && tmpMoney > mat[tmpTime][adjacent[j][k].first][0]) {
  42.                         if (tmpMoney > maxMoney) maxMoney = tmpMoney; // actualizam maximul
  43.                         mat[tmpTime][adjacent[j][k].first][0] = tmpMoney; // evenimentul in matrice
  44.                         for (int l = 1; l <= nodes; ++l) { // dar si lantul de noduri vizitate
  45.                             mat[tmpTime][adjacent[j][k].first][l] = mat[i][j][l];
  46.                             mat[tmpTime][adjacent[j][k].first][adjacent[j][k].first] = 1;
  47.                         }
  48.                     }
  49.                 }
  50.             }
  51.         }
  52.     }
  53. }
  54.  
  55.  
  56. int main()
  57. {
  58.     //freopen("dp_graf.in", "rt", stdin); // switch input source
  59.     parse_input();
  60.     solve();
  61.     cout << maxMoney;
  62.     return 0;
  63. }
  64.  
stdin 
7 9 1 4
10 20 40 10 200 20 1
1 1 2
1 2 3
2 1 3
1 1 6
1 6 7
1 7 5
1 3 7
1 3 4
2 4 5
compilation info 
prog.cpp: In function ‘void solve()’:
prog.cpp:35: warning: comparison between signed and unsigned integer expressions
stdout 
271
https://ideone.com/bJLUt
language:
C++ (gcc 8.3)
created:
13 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!