1042.The Lightest Cycle

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#define inf 0x3fffffff
using namespace std;

struct node {
    node(int num, int len) {
        this->num = num;
        this->len = len;
    }
    int num;
    int len;
};

vector<node> nt[100];
bool mark[100];
int a[100][100];
int n, ans = inf;

void recur(int r, int u, int nr, int len) {
    if (nr >= 2 && a[u][r] != inf)
        ans = min(ans, len + a[u][r]);
    for (vector<node>::iterator it = nt[u].begin(); it != nt[u].end(); it++) {
        if (!mark[it->num] && len + it->len < ans) {
            mark[it->num] = true;
            recur(r, it->num, nr + 1, len + it->len);
            mark[it->num] = false;
        }
    }
}

int main(int argc, char* argv[]) {
    int m, i, j;
    int u, v, len;

    scanf("%d %d", &n, &m);
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            a[i][j] = i == j ? 0 : inf;
    while (m--) {
        scanf("%d %d %d", &u, &v, &len);
        nt[u].push_back(node(v, len));
        a[u][v] = len;
    }

    for (i = 0; i < n; i++) {
        mark[i] = true;
        recur(i, i, 0, 0);
        mark[i] = false;
    }
    printf("%d\n", ans != inf ? ans : -1);

    return 0;
}