Submission #1372949

---

Source Code Expand

#include <iostream>
using namespace std;

const int INF = 1e9;

int main() {
  int N, M;
  cin >> N >> M;
  int cost[N][N], cost0_[N];
  // ワーシャルフロイドのための初期化
  for (int i = 0; i < N; i++) {
    cost0_[i] = i == 0 ? 0 : INF;
    for (int j = 0; j < N; j++) {
      cost[i][j] = i == j ? 0 : INF;
    }
  }
  int u, v, l;
  for (int i = 0; i < M; i++) {
    cin >> u >> v >> l;
    if (u - 1 == 0) cost0_[v-1] = l;
    else cost[u-1][v-1] = cost[v-1][u-1] = l;
  }

  // ワーシャルフロイド法で全頂点間の最短経路を求める
  for (int k = 0; k < N; k++) {
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
      }
    }
  }

  // 点0から点0の隣接点までの距離 + その点から点0の他の隣接点までの最短距離 + その点から点0までの距離、の最小を求める
  int ans = INF;
  for (int i = 1; i < N; i++) {
    if (cost0_[i] == INF) continue;
    for (int j = 1; j < N; j++) {
      if (i == j) continue;
      ans = min(ans, cost0_[i] + cost[i][j] + cost0_[j]);
    }
  }

  // 解答
  cout << (ans == INF ? -1 : ans) << endl;
  return 0;
}

Submission Info

Judge Result