C - Blue Bird / AtCoderBeginnerContest#022
#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を出力。
〜了〜