C - Blue Bird / AtCoderBeginnerContest#022

abc022.contest.atcoder.jp

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

#define INF (1<<29)

int d[300][300];

void Warshall_Floyd(int n)
{
	for (int k=1; k<n; ++k)
		for (int i=1; i<n; ++i)
			for (int j=1; j<n; ++j)
				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}

void Solve(int n, int m)   {
    int u, v, l, tmp[300][300], answer=INF;

    for (int i=0; i<n; ++i)
        for (int j=0; j<n; ++j)
            d[i][j]=tmp[i][j]=INF;
    for (int i=0; i<m; ++i) {
        cin >> u >> v >> l;
        d[u-1][v-1]=d[v-1][u-1]=l;
        tmp[u-1][v-1]=tmp[v-1][u-1]=l;
    }
    Warshall_Floyd(n);
    for (int i=1; i<n; ++i)
        for (int j=i+1; j<n; ++j)
            answer=min(answer,d[i][j]+tmp[0][i]+tmp[0][j]);
    if (answer == INF)  answer=-1;
    cout << answer << endl;
}

int main(void)  {
    int n, m;

    cin >> n >> m;
    Solve(n,m);
    return 0;
}

予め自分の家に隣接する道以外の最短経路を求めておき、次に家に隣接する道のうち2つを閉路に含めるかを試し、最後に最適な経路を選べる場合は道の長さを出力、無理な場合は-1を出力。
〜了〜