cpp.cpp

#define _POSIX_C_SOURCE 200809L
#include <chrono>
#include <vector>
#include <bitset>
#include <fstream>
#include <iostream>
#include <string>

using namespace std;
using namespace std::chrono;

struct route{
	int dest, cost;
};

struct node {
	vector<route> neighbours;
};

vector<node> readPlaces(){
	ifstream text("agraph");
	string numNodesText;
	text >> numNodesText;
	int numNodes = stoi(numNodesText);
	vector<node> nodes(numNodes);
	string nodeS, neighbourS, costS;
	while (text >> nodeS >> neighbourS >> costS){
		nodes[stoi(nodeS)].neighbours.push_back(route{ stoi(neighbourS), stoi(costS) });
	}
	return nodes;
}

inline int getLongestPath(vector<node> &nodes, int nodeID, vector<int> &visited){
	visited[nodeID] = 1;
	int max = 0;
	for (const route& neighbour : nodes[nodeID].neighbours){
		if (visited[neighbour.dest] == 0){
			int dist = neighbour.cost + getLongestPath(nodes, neighbour.dest, visited);
			if (dist > max){ 
				max = dist;
			}
		}
	}
	visited[nodeID] = 0;
	return max;
}

int main(int argc, char** argv){
	auto nodes = readPlaces();
	vector<int> visited(nodes.size(), 0);
	auto start = high_resolution_clock::now();
	int len = getLongestPath(nodes, 0, visited);
	auto duration = high_resolution_clock::now() - start;
	cout << len << " LANGUAGE C++ " << duration_cast<milliseconds>(duration).count() << "\n";
}