Shortest path : Floyd Warshall - YessineJallouli/Competitive-Programming GitHub Wiki

#include <bits/stdc++.h>
#define ll long long
#define SaveTime ios_base::sync_with_stdio(false), cin.tie(0);
using namespace std;

const ll inf = LLONG_MAX;
const int N = 507;
ll dist[N][N];
int n;

int main() {
   SaveTime
   int m; cin >> n >> m;
   for (int i = 1; i <= n; ++i) {
      for (int j = 1; j<= n; j++)
         dist[i][j] = inf;
      dist[i][i] = 0;
   }
   for (int i = 0; i < m; i++) {
      int a,b,w; cin >> a >> b >> w;
      dist[a][b] = dist[b][a] = w;
   }
   for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++)
         for (int k = 1; k <= n; k++)
            if (dist[i][k] != inf && dist[j][i] != inf)
               dist[j][k] = min(dist[j][i] + dist[i][k], dist[j][k]);
   }
}