[C++] 백준 1959 : 운동

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

1956번: 운동

백준 1956번 운동을 풀었다.

 

dist[i][i]를 INF로 놓고 플로이드 와샬 알고리즘을 수행하면 i번 노드에서 i번 노드로 가는 최소 비용이 dist[i][i]에 저장된다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <vector>
#pragma warning(disable:4996)
using namespace std;

#define INF 10000000

int adj[401][401];
int dist[401][401];

int main() {
	int v, e;
	cin >> v >> e;

	int start, end, cost;
	for (int i = 1; i <= e; i++) {
		scanf("%d %d %d", &start, &end, &cost);
		adj[start][end] = cost;
	}

	for (int i = 1; i <= v; i++) {
		for (int j = 1; j <= v; j++) {
			if (i == j)
				dist[i][j] = INF;
			else if (adj[i][j] != 0)
				dist[i][j] = adj[i][j];
			else
				dist[i][j] = INF;
		}
	}

	for (int k = 1; k <= v; k++) {
		for (int i = 1; i <= v; i++) {
			for (int j = 1; j <= v; j++)
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
		}
	}

	int flag = 0;
	int min = INF;
	for (int i = 1; i <= v; i++) {
		if (dist[i][i] == INF)
			continue;
		else {
			flag = 1;
			if (min > dist[i][i])
				min = dist[i][i];
		}
	}

	if (flag == 0)
		cout << "-1";
	else
		cout << min;

	return 0;
}