ABC 22 C - Blue Bird ( Floyd Warshall )

C: Blue Bird - AtCoder Beginner Contest 022 | AtCoder
Problem Statement: Given a graph of n ≤ 300 nodes and some edges, find the minimum weight sum of a cycle that starts from 1, goes to some other nodes and end in 1.
Basically, we will be finding a cycle that contains node 1. Definitely, there will be exactly 2 nodes connected with 1, one for out and one for in. We can simply enumerate these 2 nodes with O( n ^ 2 ), and update the minimum. We will use Floyd-Warshall algorithm to pre-calculate distance for each pair of nodes in O( n ^ 3 ). Note that this pre-calculated distance should not pass node 1 at all.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300 + 2;
const int MAXM = MAXN * MAXN / 2;
const int MAXW = 1e5 + 5;
const int INF = 0x3f3f3f3f;

void upmin(int &x, int v){ if( x > v ) x = v; }

struct Edge{
    int u, v, w;
    Edge(int _u = 0, int _v = 0, int _w = 0): u(_u), v(_v), w(_w){}
} es[ MAXM * 2 ];

int n, m;
vector<int> G[ MAXN ];

int dis[ MAXN ][ MAXN ];

void solve(){
    memset( dis, INF, sizeof(dis) );
    for(int i = 1; i <= n; ++i) dis[ i ][ i ] = 0;
    for(int i = 1; i <= m; ++i)
        dis[ es[ i ].u ][ es[ i ].v ] = 
        dis[ es[ i ].v ][ es[ i ].u ] = es[ i ].w;
    for(int k = 2; k <= n; ++k)
        for(int i = 2; i <= n; ++i)
            for(int j = 2; j <= n; ++j)
                upmin( dis[ i ][ j ], dis[ i ][ k ] + dis[ k ][ j ] );
    int ans = INF;
    for(int i = 0; i < G[ 1 ].size(); ++i){
        int u = es[ G[ 1 ][ i ] ].v;
        for(int j = 0; j < G[ 1 ].size(); ++j){
            int v = es[ G[ 1 ][ j ] ].v;
            if( u == v ) continue;
            upmin( ans, es[ G[ 1 ][ i ] ].w + dis[ u ][ v ] + es[ G[ 1 ][ j ] ].w );
        }
    }
    if( ans == INF ) ans = -1;
    printf("%d\n", ans);
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; ++i){
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        es[ i ] = Edge( u, v, w );
        G[ u ].push_back( i );
        es[ i * 2 ] = Edge( v, u, w );
        G[ v ].push_back( i * 2 );
    }
    solve();
    return 0;
}