티스토리 뷰
반응형
백준 1916번 최단경로
https://www.acmicpc.net/problem/1916
정답 코드
#include <iostream>
using namespace std;
int INF = 987654321;
int arr[1001][1001];
bool v[1001];
int d[1001];
int n, m, a, b, c, s, e;
int getSmallIndex() {
int min = INF;
int index = 1;
for (int i = 1; i <= n; i++)
{
if (d[i] < min && !v[i]) {
min = d[i];
index = i;
}
}
return index;
}
void dijkstra(int start) {
for (int i = 1; i <= n; i++) {
d[i] = arr[start][i];
}
v[start] = 1;
for (int i = 1; i <= n - 2; i++)
{
int current = getSmallIndex();
v[current] = 1;
for (int j = 1; j <= n; j++)
{
if (!v[j]) {
if (d[current] + arr[current][j] < d[j]) {
d[j] = d[current] + arr[current][j];
}
}
}
}
}
int main() {
for (int i = 1; i < 1001; i++)
for (int j = 1; j < 1001; j++)
arr[i][j] = INF;
cin >> n >> m;
for (int i = 0; i < m; i++)
{
cin >> a >> b >> c;
if (arr[a][b] > c)
arr[a][b] = c;
}
cin >> s >> e;
dijkstra(s);
cout << d[e];
}
문제 풀이
다익스트라 알고리즘을 이용해서 풀 수 있는 문제입니다. 저는 바킹둑님의 강의를 보고 코드를 구현했습니다!
반응형
'Algorithm > BOJ' 카테고리의 다른 글
백준 1926번 C++ (0) | 2023.08.03 |
---|---|
백준 1920번 C++ (0) | 2023.08.02 |
백준 1914번 C++ (0) | 2023.07.30 |
백준 1912번 C++ (0) | 2023.07.30 |
백준 1904번 C++ (0) | 2023.07.30 |
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 에라토스테네스의 체
- HTML5
- 자료구조
- 최단 경로
- java
- BFS
- 투 포인터
- Do it!
- C++
- 카운팅 정렬
- DFS
- 자바
- 백준
- 유클리드 호제법
- c++ string
- js
- 반복문
- 이분 매칭
- 자바스크립트
- C++ Stack
- 알고리즘 공부
- html
- 세그먼트 트리
- 백준 풀이
- 유니온 파인드
- 알고리즘
- CSS
- 스택
- 우선순위 큐
- DP
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함