VioletaBabel
플로이드-와샬 알고리즘 본문
#include <cstdio>#include <algorithm>using namespace std;#define inf 1000000000int main(){ // n은 점 갯수, m은 선 갯수, a는 출발점, b는 도착점, c는 가중치값int n, m, a, b, c, route[101][101];scanf("%d %d", &n, &m);fill_n(&route[0][0], 10201, inf);for (int i = 1; i <= n; ++i)route[i][i] = 0;for (int i = m; i--; route[a][b] = min(route[a][b], c))scanf("%d %d %d", &a, &b, &c);for (int k = 1; k <= n; ++k)for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j)route[i][j] = min(route[i][j], route[i][k] + route[k][j]);for (int i = 1; i <= n; ++i, printf("\n"))for (int j = 1; j <= n; ++j)printf("%d ", route[i][j]);}
'알고리즘' 카테고리의 다른 글
원형 큐 (c/c++) (0) | 2018.12.06 |
---|---|
세그먼트 트리 (0) | 2017.06.19 |
최대공약수, 최소공배수 (0) | 2017.05.28 |
[C++/함수]에라토스테네스의 체 (0) | 2017.05.28 |
단순한 이진트리 코드 (0) | 2017.04.29 |
Comments