알고리즘/최단 경로

백준 - 1504

2023. 7. 7. 15:21
목차
  1. 문제
  2. 문제 풀이

문제

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

1 → u → v → N (혹은 1 → v → u → N)의 최단 경로의 길이를 찾는 문제였다.

 

문제 풀이

플루이드 워셜 알고리즘을 이용해 풀었다. 처음에 1 → u → v → N 경우에 대해서만 최솟값을 찾아줘서 틀렸는데 1 → v → u → N 경우와도 비교해 최솟값을 구해서 맞췄다. MAX_INT 값은 간선의 최대 길이인 1000 * 간선의 최대 개수인 200000을 해준 200000000보다 큰 값으로 정해줬다.

 

MAX_INT 값을 3번 더해도 6억이라 int 범위를 넘어서지 않아서 long long 대신 int로 선언해도 문제는 없을 것 같다.

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include<iostream>
using namespace std;
#define MAX_INT 300000000
long long map[801][801];
int main()
{
int N, E;
int i, j, k;
int a, b, c;
int u, v;
long long minDist;
scanf("%d %d", &N, &E);
for (i = 0; i <= N; i++) {
for (j = 0; j <= N; j++) {
if (i == j) {
map[i][j] = 0;
continue;
}
map[i][j] = MAX_INT;
}
}
for (i = 0; i < E; i++) {
scanf("%d %d %d", &a, &b, &c);
map[a][b] = c;
map[b][a] = c;
}
scanf("%d %d", &u, &v);
for (k = 1; k <= N; k++) {
for (i = 1; i <= N; i++) {
for (j = 1; j <= N; j++) {
map[i][j] = min(map[i][k] + map[k][j], map[i][j]);
}
}
}
minDist = map[1][u] + map[u][v] + map[v][N];
minDist = min(minDist, map[1][v] + map[v][u] + map[u][N]);
if (minDist >= MAX_INT) printf("-1");
else printf("%.lld", minDist);
return 0;
}
/*
4 3
1 2 2
1 3 1
2 4 3
1 3
7
*/
  1. 문제
  2. 문제 풀이
'알고리즘/최단 경로' 카테고리의 다른 글
  • 프로그래머스 - 배달
  • 백준 - 1238
  • [이코테] 실전 문제
  • 최단 경로
hahihi
hahihi
hahihi
히호 노트
hahihi
전체
오늘
어제
  • 분류 전체보기 (224)
    • 알고리즘 (114)
      • 정렬 (3)
      • 그리디 (9)
      • 구현 (35)
      • 이분 탐색 (4)
      • 탐색 (2)
      • 동적 계획법 (DP) (11)
      • DFS BSF (29)
      • 최단 경로 (5)
      • 그래프 (4)
      • 주의할 점 (4)
      • 트리 (3)
    • spring (34)
      • JPA (12)
    • DevOps (10)
      • Docker (3)
    • java (15)
      • 이펙티브자바 (4)
      • Clean Code (4)
    • git (9)
    • DB (3)
    • 앱개발 (1)
    • 유닉스 (26)
    • 네트워크 (3)
      • IT 엔지니어를 위한 네트워크 입문 (3)
    • 유니티 (1)
    • 후기 (4)
    • 누누코코 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • Docker
  • 이코테
  • 1868
  • 도넛과 막대 그래프
  • JWT
  • 그리디 알고리즘
  • SWEA
  • dp
  • 백준
  • 7465
  • 숫자 조각
  • BaseEntity
  • 4193
  • 팀 결성
  • 입출력
  • allowPublicKeyRetrieval
  • 프로그래머스
  • 공통 response
  • 13265
  • spring

최근 댓글

최근 글

hELLO · Designed By 정상우.
hahihi
백준 - 1504
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.