Lennot

#include <iostream>
#include <vector>
using namespace std;

vector<pair<int, long long>> f[100000];
bool co[100000];
bool ce[100000];
long long po[100000];
long long pe[100000];
int n, m = 0;
long long output = 9223372036854775807LL;

void search(int d, long long p, bool o);

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		co[i] = false;
		ce[i] = false;
		po[i] = 9223372036854775807LL;
		pe[i] = 9223372036854775807LL;
	}
	for (int i = 0; i < m; i++) {
		int a, b = 0;
		long long h = 0;
		cin >> a >> b >> h;
		a--;
		b--;
		f[a].push_back(make_pair(b, h));
	}
	search(0, 0, true);
	cout << output;
	return 0;
}

void search(int d, long long p, bool o) {
	if (d == n - 1) {
		if (p < output) {
			output = p;
		}
	}
	if ((o && co[d]) || (!o && ce[d])) {
		return;
	}
	if (o) {
		co[d] = true;
		po[d] = p;
	}
	else {
		ce[d] = true;
		pe[d] = p;
	}
	for (int i = 0; i < (int)f[d].size(); i++) {
		if (o) {
			if (p + f[d][i].second < pe[f[d][i].first]) {
				search(f[d][i].first, p + f[d][i].second, !o);
			}
		}
		else {
			if (p < po[f[d][i].first]) {
				search(f[d][i].first, p, !o);
			}
		}
	}
	if (o) {
		co[d] = false;
	}
	else {
		ce[d] = false;
	}
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: ACCEPTED

Test 16

Group: 3

Verdict: ACCEPTED

Test 17

Group: 3

Verdict: TIME LIMIT EXCEEDED