어흥
[백준 1956] 운동 (C++) 본문
728x90
반응형
문제 링크: https://www.acmicpc.net/problem/1956
1. 주의할 점
- 플로이드와샬 알고리즘에 대해 알고 있어야 한다
2. 구현
- Node, Edge의 수를 입력 받은 후, Arr[][]배열을 초기화한다
- 플로이드 와샬 알고리즘을 통해 Arr[i][j]를 갱신한다(i에서 j까지의 최단거리)
- Result 변수를 두어 i->j->i까지 거리를 비교하고, Result가 초기 설정값과 같다면 -1을 할당한다
#define MAX 9876543210
#include <iostream>
#include <algorithm>
using namespace std;
int node, edge, s, e, val;
long long arr[401][401];
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> node >> edge;
for(int i=1;i<=node;i++)
for (int j = 1; j <= node; j++) {
if (i == j) arr[i][j] = 0;
else arr[i][j] = MAX;
}
for (int i = 0; i < edge; i++) {
cin >> s >> e >> val;
arr[s][e] = val;
}
for (int k = 1; k <= node; k++) {
for (int i = 1; i <= node; i++) {
for (int j = 1; j <= node; j++) {
arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
}
}
}
long long result = MAX;
for (int i = 1; i <= node; i++)
for (int j = 1; j <= node; j++) {
if (i == j) continue;
result = min(result, arr[i][j] + arr[j][i]);
}
if (result == MAX) result = -1;
cout << result;
system("pause");
return 0;
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 13905] 세부 (C++) (0) | 2020.06.02 |
---|---|
[백준 11085] 군사 이동 (C++) (0) | 2020.05.26 |
[백준 3709] 레이저빔은 어디로 (C++) (0) | 2020.05.25 |
[백준 17835] 면접보는 승범이네 (C++) (0) | 2020.05.24 |
[백준 2470] 두 용액 (C++) (0) | 2020.05.23 |
Comments