GRL_1_C All Pairs Shortest Paths

Calendar Clock iconCalendar Clock icon

AOJ

Table of contents

# Solution

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

#define MAX_N 101
#define MAX_E 9901
#define W_INF (1L << 32)

Int dist[MAX_N][MAX_N];
bool negative = false;

void apsp(Int n) {
  loop(k,0,n) {
    loop(u,0,n) {
      if (dist[u][k] == W_INF) continue;
      loop(v,0,n) {
        if (dist[k][v] == W_INF) continue;
        dist[u][v] = min(dist[u][v], dist[u][k] + dist[k][v]);
      }
      
      if (dist[u][u] < 0) {
        negative = true;
        return;
      }
    }
  }
}


int main(void) {
  Int n, e, v, u, w;
  cin >> n >> e;
  loop(i,0,n) {
    loop(j,0,n) {
      dist[i][j] = (i == j) ? 0 : W_INF;
    }
  }
  
  loop(i,0,e) {
    cin >> u >> v >> w;
    dist[u][v] = w;
  }
  
  apsp(n);
  if (negative) cout << "NEGATIVE CYCLE" << endl;
  else {
    loop(u,0,n) {
      loop(v,0,n) {
        if (dist[u][v] == W_INF) cout << "INF";
        else cout << dist[u][v];
        if (v != n-1) cout << ' ';
      }
      cout << endl;
    }
  }
}
 

Remote freelancer. A web and mobile application enginner.
Traveling around the world based on East Asia.
I'm looking forward to your job offers from all over the world!

Offer jobs or contact me!

Comments