본문 바로가기

Dijkstra

 (8)
[BOJ] 1261번 알고스팟 (C++) https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net #include #include #define INF 987654321 using namespace std; int M, N; int dy[4] = { 1, -1, 0, 0 }; int dx[4] = { 0, 0, 1, -1 }; int arr[101][101]; int dist[101][101]; void dijkstra() { queue pq; pq.push({ 0, 0 ..
[BOJ] 1504번 특정한 최단 경로 (C++) https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net #include #include #include #include #define MAX 801 #define INF 987654321 using namespace std; vector v[MAX]; int d[MAX]; int n, e; int v1, v2; void dijkstra(int start){ for(int i = 0; i start_to_ne..
[BOJ] 23793번 두 단계 최단 경로 1 (C++) https://www.acmicpc.net/problem/23793 23793번: 두 단계 최단 경로 1 서준이는 아빠로부터 생일선물로 세계 지도를 받아서 매우 기뻤다. 세계 지도에서 최단 경로를 찾는 프로그램을 개발해서 아빠께 감사의 마음을 전달하려고 한다. 세계 지도는 도시를 정점으 www.acmicpc.net #include #include #include #define INF 2e9 #define MAX 100001 #define MAX_EDGE 200001 using namespace std; int n, m, x, y, z; int d[MAX]; vector v[MAX_EDGE]; void dijkstra(int start){ for(int i = 0; i start_to_next_dis){ ..
[BOJ] 1238번 파티 (C++) https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net #include #include #include #define INF 987654321 #define MAX 1001 #define MAX_EDGE 10001 using namespace std; int n, m, x; int d[MAX]; vector v[MAX_EDGE]; void dijkstra(int start){ for(int i = 1; i > n >> m..
[BOJ] 11779번 최소비용 구하기 2 (C++) https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net #include #include #include #include #define MAX_EDGE 1001 #define MAX 100001 #define INF 987654321 using namespace std; int d[MAX]; int pv[MAX]; vector v[MAX_EDGE]; stack st; void dijkstra(int start){ d[st..
[BOJ] 9694번 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 (C++) https://www.acmicpc.net/problem/9694 9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 맨위 첫 번째 줄에 T(1 > t; for(int k = 0; k > n >> m; for(int i = 0; i > a >> b >> c; v[a].push_back({c, b}); v[b].push_back({c, a}); } dijkstra(); cout
[BOJ] 5972번 택배 배송 (C++) https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net #include #include #include #define MAX_VERTEX 50001 #define MAX 50001 #define INF 987654321 using namespace std; int n, m; int d[MAX_VERTEX]; vector edge[MAX]; void dijkstra(){ d[1] = 0; priority_queue pq; pq.push({0, 1}); while..
[BOJ] 1753번 최단경로 (C++) https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net #include #include #include #define INF 987654321 #define MAX_VERTEX 20001 #define MAX_EDGE 300001 using namespace std; // 최소 비용 배열 int d[MAX_VERTEX]; // 간선 정보를 담은 Vector 생성 // index : 시작 노드, value : pai..

티스토리툴바