CFR 602 C. The Two Routes ( Floyd Warshall )

Problem - C - Codeforces
It's easy to see it is a complete graph, which means there exists exactly one path that could carry one from the start to the end. So the actual answer is quite simple, the maximum among the two shortest paths.
Default codeを持つことを始めた。しばらくは自分のライブラリを埋めていこう。

const int MAXN = 400 + 2;
const int MAXM = MAXN * MAXN / 2;

int n, m;
vector< Edge > e1, e2;

void init(){
    scanf("%d%d", &n, &m);
    set< pii > vis;
    rep( i, 0, m ){
         int u, v; scanf("%d%d", &u, &v);
         --u, --v;
         vis.insert( pii( u, v ) );
         vis.insert( pii( v, u ) );
         e1.push_back( Edge( u, v ) );
    }
    rep( u, 0, n )
        rep( v, u + 1, n )
            if( !vis.count( pii( u, v ) ) )
                e2.push_back( Edge( u, v ) );
}

FloydWarshall fw1, fw2;
void solve(){
    fw1.init( n );
    fw1.solve( e1 );
    fw2.init( n );
    fw2.solve( e2 );
    int ans = max( fw1.dis[ 0 ][ n - 1 ], fw2.dis[ 0 ][ n - 1 ] );
    if( ans == INF ) ans = -1;
    printf("%d\n", ans);
}