Permalink
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
57 lines (44 sloc) 1.48 KB
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
using namespace std;
//a fellow student suggested dijkstra invented this
// particular algorithm. It sounds cool, so that's
// what I named it.
int dijkstra_max(int A[], int rows) {
int length = rows * (rows+1) / 2;
//we iterate backwards through the pyramid, row by row
for (int l = 98; l > 0; l--) {
//we find the first and last index for the current row
int indexlow = (l * (l+1))/2;
int indexhigh = (l * (l+3))/2;
//for each index in the current row...
for (int index = indexlow; index <= indexhigh; index++) {
//...we add its value to the maximum of its children's values
A[index] = A[index] + max(A[index+l+1], A[index+l+2]);
}
}
//finally, the highest of the two values in row 1 are added to the
//value at the top, giving us the value of the maximum path
A[0] = A[0] + max(A[1], A[2]);
return A[0];
}
int main() {
string filename = "euler_67.txt";
ifstream myfile;
myfile.open(filename);
string line;
//this works for up to 100 rows (101*100/2).
// a better solution would be to use a dynamic array.
int A[5050];
int i = 0;
//assuming we have well-formed input data, a tree
// can be quickly and easily stored sequentially
// in an array.
while(myfile >> line) {
A[i] = stoi(line);
i++;
}
cout << dijkstra_max(A, 100) << '\n';
return 0;