Submission #1691181

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;

using ll = long long;
using P = pair<int, int>;

// 4近傍、8近傍
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

const int INF = 1e9;
int N, M;
int edge[310][310];
int dist[310];

void dijkstra(int s) {
  dist[s] = 0;
  priority_queue<P, vector<P>, greater<P> > que;
  P cur = P(0, s);
  que.push(cur);

  while (!que.empty()) {
    cur = que.top();
    que.pop();

    int from = cur.second;
    for (int i = 0; i < N; i++) {
      if (edge[from][i] == 0) continue;

      if (dist[i] > dist[from] + edge[from][i]) {
        dist[i] = dist[from] + edge[from][i];
        que.push(P(dist[i], i));
      }
    }
  }
}

int main() {
  // 入力
  cin >> N >> M;
  int u, v, l;
  for (int i = 0; i < M; i++) {
    cin >> u >> v >> l;
    u--; v--;
    edge[u][v] = edge[v][u] = l;
  }

  // ダイクストラ法で最短距離を探す
  int ans = INF;
  for (int i = 1; i < N; i++) {
    if (edge[0][i] == 0) continue;

    int tmp = edge[0][i];
    edge[0][i] = edge[i][0] = 0;
    fill(dist, dist + 310, INF);
    dijkstra(i);
    if (dist[0] != INF) ans = min(ans, dist[0] + tmp);
    edge[0][i] = edge[i][0] = tmp;
  }

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

  return 0;
}

Submission Info

Judge Result