RACE bellman Ford

#include <iostream>

#include <fstream>

using namespace std;

fstream fin;

int d[1000];

int p[1000];

int t[1000];

int dist[1000];

int T;

int n;

void bf(int u, int v, int c)

{

   if (d[v] > d[u] + c)

   { 

  d[v] = d[u] + c;

       p[v] = u; 

   }

}

int main()

{

fin.open("input.txt");

fin >> T >> n;

for(int i = 1; i <= n + 1; i ++)

fin >> dist[i];

for(int i = 1; i <= n; i ++)

fin >> t[i];

t[n + 1] = 0;

for(int i = 0; i <= n; i ++) {

d[i] = 987654321;

p[i] = -1;

}

d[0] = 0;

for(int i = 0;  i <= n; i ++) {

int localLen = 0;

for(int j = i + 1; j <= n + 1; j ++) {

localLen += dist[j];

if(localLen > T)

break;

bf(i, j, t[j]);

}

}

int head = n;

int sumtime = 0;

int ans[100];

int iter = 0;

while(head != 0)

{

sumtime += t[head];

ans[iter++] = head;

head = p[head];

}

cout << sumtime << endl;

cout << iter << endl;

for(int i = iter - 1; i >= 0; i --)

{

cout << ans[i] << " ";

}

cout << endl;

return 0;

}