[11404] 플로이드

• 입력: 도시 수 N 버스 수 M 출발 도시와 도착 도시 (u,v) 버스 비용 c
• 출력: 모든 도시 쌍을 이동하는 데 드는 최소 비용
• 알고리즘: Floyd-Warshall
• 소스코드
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <vector> #include <limits.h> using namespace std; #define INT_MAX 100*100*1000 + 1 int min(int a, int b) { return (a < b ? a : b); } int main() { int n, m, u, v, c; scanf("%d %d", &n, &m); vector<vector<int> > adj(n + 1, vector<int>(n + 1, INT_MAX)); for (int i = 1; i <= n; i++) adj[i][i] = 0; for (int i = 0; i < m; i++) { scanf("%d %d %d", &u, &v, &c); adj[u][v] = min(adj[u][v],c); } for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { if (i == k) continue; for (int j = 1; j <= n; j++) { adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]); } } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { printf("%d ", (adj[i][j] == INT_MAX ? 0 : adj[i][j])); } printf("\n"); } return 0; }
• 문제 참고: https://www.acmicpc.net/problem/11404
  
• 알고리즘 참고: Floyd-Warshall