2016. 7. 23. 01:24
Algorithm/기본 이론
floyd warshall인가.. 이게 중요함. 느려도 이거 쓰면 편하게 구할 수 있음.
#include<stdio.h>
int
s[110][110], p[110][110], n, m;
void
path(
int
s,
int
e)
{
if
(p[s][e] == 0)
return
;
path(s, p[s][e]);
printf
(
"%d "
, p[s][e]);
path(p[s][e], e);
}
int
main()
{
/*
5 5
0 2 2 5 9
2 0 3 4 8
2 3 0 7 6
5 4 7 0 5
9 5 6 5 0
*/
int
i, j, k;
scanf
(
"%d %d"
, &n, &m);
for
(i = 1; i <= n; i++){
for
(j = 1; j <= n; j++) {
scanf
(
"%d"
, &s[i][j]);
}
}
for
(k = 1; k <= n; k++) {
for
(i = 1; i <= n; i++) {
for
(j = 1; j <= n; j++) {
if
(s[i][j] > s[i][k] + s[k][j]) {
s[i][j] = s[i][k] + s[k][j];
p[i][j] = k;
}
}
}
}
printf
(
"%d\n"
, s[1][m]);
printf
(
"1 "
);
path(1, m);
printf
(
"%d "
, m);
return
0;
}
'Algorithm > 기본 이론' 카테고리의 다른 글
순열, 중복순열, 조합, 중복조합 (0) | 2016.08.06 |
---|---|
공부 순서 (0) | 2016.06.13 |
bubble sort (0) | 2016.03.12 |
default (0) | 2016.02.27 |