Submission #2238814

---

Source Code Expand

#include <iostream>
#include<string>
#include <stdlib.h>
#include <cmath>
#include <vector>

int main(int argc, char const *argv[]) {
  int N = 310, M = 45000;
  int dist[N][N];
  std::cin >> N >> M;

  for(int i = 1; i <= N; i++){
    for(int j = 1; j <= N; j++){
      if(i != j) dist[i][j] = 500000;
      else dist[i][j] = 0;
    }
  }
  for(int i = 1; i <= M; i++){
    int a, b, t;
    std::cin >> a >> b >> t;
    dist[a][b] = t;
    dist[b][a] = t;
  }
  // for(int i = 1; i <= N; i++){
  //   for(int j = 1; j <= N; j++){
  //     std::cout << dist[i][j] << " ";
  //   }
  //   std::cout << '\n';
  // }

  for(int k = 1; k <= N; k++) {
    for(int i = 1; i <= N; i++){
      for(int j = 1; j <= N; j++){
        dist[i][j] = std::min(dist[i][j] , dist[i][k] + dist[k][j]);
      }
    }
  }
  int min = 5000000;
  for(int i = 1; i <= N; i++){
    int max = 0;
    for(int j = 1; j <= N; j++){
      max = std::max(dist[i][j], max);
    }
    min = std::min(min, max);
  }
  std::cout << min << '\n';
  return 0;
}

Submission Info

Judge Result