BOJ. Exercise (1956)

Problem link

Let dist[u][v] be the shortest known directed distance from vertex u to vertex v. Initialize every entry to infinity, set dist[i][i] = 0, and record the minimum weight among parallel direct edges. Keeping the diagonal at zero makes the empty path available to Floyd–Warshall; direct self-loops are retained separately as edges for cycle evaluation.

Floyd–Warshall considers each vertex k as an allowed intermediate vertex. For each pair (u, v), a shortest route either avoids k or goes from u to k and then from k to v, so update dist[u][v] with dist[u][k] + dist[k][v]. Skip the addition if either partial route is unreachable. Afterward, every directed edge u -> v with weight w closes a cycle exactly when a route exists from v back to u; that cycle has length w + dist[v][u]. Taking the minimum over all edges finds the shortest cycle. If no edge has a return route, there is no cycle and the answer is -1. This also handles a self-loop (u == v) and parallel edges.

The Floyd–Warshall phase takes O(V^3) time, and scanning the edge matrix takes O(V^2) time. The distance and edge matrices use O(V^2) space. long distances and an infinity sentinel of Long.MAX_VALUE / 4 leave ample room for sums; unreachable partial paths are checked before addition.

import java.io.*;
import java.util.*;

public class Main {
  static class FastScanner {
    private final InputStream input;
    private final byte[] buffer = new byte[1 << 16];
    private int length = 0;
    private int pointer = 0;

    FastScanner(InputStream input) {
      this.input = input;
    }

    private int read() throws IOException {
      if (pointer == length) {
        length = input.read(buffer);
        pointer = 0;
        if (length == -1) return -1;
      }
      return buffer[pointer++];
    }

    int nextInt() throws IOException {
      int c;
      do {
        c = read();
      } while (c <= ' ' && c != -1);

      int value = 0;
      while (c > ' ') {
        value = value * 10 + c - '0';
        c = read();
      }
      return value;
    }
  }

  public static void main(String[] args) throws IOException {
    FastScanner input = new FastScanner(System.in);
    int v = input.nextInt();
    int e = input.nextInt();
    long infinity = Long.MAX_VALUE / 4;
    long[][] edge = new long[v][v];
    long[][] dist = new long[v][v];

    for (int i = 0; i < v; i++) {
      Arrays.fill(edge[i], infinity);
      Arrays.fill(dist[i], infinity);
      dist[i][i] = 0;
    }

    for (int i = 0; i < e; i++) {
      int from = input.nextInt() - 1;
      int to = input.nextInt() - 1;
      long weight = input.nextInt();
      edge[from][to] = Math.min(edge[from][to], weight);
      dist[from][to] = Math.min(dist[from][to], weight);
    }

    for (int mid = 0; mid < v; mid++) {
      for (int from = 0; from < v; from++) {
        if (dist[from][mid] == infinity) continue;
        for (int to = 0; to < v; to++) {
          if (dist[mid][to] == infinity) continue;
          dist[from][to] = Math.min(
              dist[from][to], dist[from][mid] + dist[mid][to]);
        }
      }
    }

    long answer = infinity;
    for (int from = 0; from < v; from++) {
      for (int to = 0; to < v; to++) {
        if (edge[from][to] == infinity || dist[to][from] == infinity) continue;
        answer = Math.min(answer, edge[from][to] + dist[to][from]);
      }
    }

    System.out.println(answer == infinity ? -1 : answer);
  }
}