블로그 이미지
shadowchaser
이곳 저곳 이것 저것

calendar

1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31

Notice

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
posted by shadowchaser