1956 운동

https://www.acmicpc.net/problem/1956

d[i][i]는 처음에 INF이므로 플로이드를 돌린 후 d[i][i]가 갱신이 되었다면 i에서 출발해서 어딘가를 돌아서 i로 다시 왔다는 의미이다. 즉, 사이클이 존재한다는 뜻이다. 갱신이 한번도 되지 않았다면 -1, 갱신이 되었다면 그 중 최소값을 출력해주면 된다.

#include <cstdio>
#include <algorithm>
#define INF 987654321
using namespace std;
 
int i,j,k,n,m,a,b,c,d[400][400],ans=INF;
 
int main()
{
    scanf("%d %d",&n,&m);
    for(i=0;i<n;i++) for(j=0;j<n;j++) d[i][j]=INF;
    while(m--)
    {
        scanf("%d %d %d",&a,&b,&c);
        if(d[--a][--b]>c) d[a][b]=c;
    }
    for(k=0;k<n;k++) for(i=0;i<n;i++) for(j=0;j<n;j++)
        d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    for(i=0;i<n;i++) ans=min(ans,d[i][i]);
    printf("%d",ans!=INF?ans:-1);
    return 0;
}