최단 경로: 간선 15개
fx-50FH II · CMPLX · 547 bytes
정점 최대 10개와 간선 15개의 무방향 네트워크에서 최소 비용 경로 하나를 구하고 정점 순서와 총비용을 표시합니다.
- 547바이트
- CMPLX 모드
풀이 예제
예제 1
대학 운용과학 창작 문제: 박물관 로봇이 번호가 붙은 전시실 사이를 이동합니다. 연결은 양방향이며 비용 단위는 분입니다. 2에서 6까지 최소 시간 경로와 총시간을 구하세요.
표시된 간선은 모두 무방향이고 표시되지 않은 연결은 없습니다. 간선표(a–b: 비용): 2–1: 7; 2–3: 4; 1–4: 5; 3–4: 2; 3–5: 8; 4–6: 3; 5–6: 2; 1–5: 12
답
표준 풀이 (계산기 없이)
- S에서 Dijkstra를 적용합니다. u는 새로 확정한 정점, d(v)는 갱신된 임시 거리, ∞는 아직 도달 불가입니다.
- u=2, d(2)=0; d(1)=7, d(3)=4
- u=3, d(3)=4; d(4)=6, d(5)=12
- u=4, d(4)=6; d(6)=9
- u=1, d(1)=7; ∅
- u=6, d(6)=9; d(5)=11
- 이전 정점을 역추적하고 경로 비용을 직접 더합니다: 2 → 3 → 4 → 6; 총비용 4+2+3=9 min
예제 2
대학 운용과학 창작 문제: 전시장 셔틀망의 요금은 정수 단위입니다. 7–8 연결은 무료로 비용이 정확히 0입니다. 7에서 2까지 최소 요금 경로와 총요금을 구하세요.
표시된 간선은 모두 무방향이고 표시되지 않은 연결은 없습니다. 간선표(a–b: 비용): 7–8: 0; 8–9: 3; 9–2: 4; 7–1: 9; 1–2: 2; 8–2: 10; 9–1: 1
답
표준 풀이 (계산기 없이)
- S에서 Dijkstra를 적용합니다. u는 새로 확정한 정점, d(v)는 갱신된 임시 거리, ∞는 아직 도달 불가입니다.
- u=7, d(7)=0; d(1)=9, d(8)=0
- u=8, d(8)=0; d(2)=10, d(9)=3
- u=9, d(9)=3; d(1)=4, d(2)=7
- u=1, d(1)=4; d(2)=6
- u=2, d(2)=6; ∅
- 이전 정점을 역추적하고 경로 비용을 직접 더합니다: 7 → 8 → 9 → 1 → 2; 총비용 0+3+1+2=6
예제 3
대학 운용과학 창작 문제: 통신 훈련망이 가상 단말 열 개를 연결합니다. 각 양방향 연결의 전송 비용은 고정된 정수입니다. 마지막 연결을 포함한 15개를 나열한 순서대로 입력하고 1에서 10까지 최소 비용 경로와 총비용을 구하세요.
표시된 간선은 모두 무방향이고 표시되지 않은 연결은 없습니다. 간선표(a–b: 비용): 1–2: 5; 2–3: 7; 3–4: 4; 4–5: 6; 5–6: 3; 6–7: 8; 7–8: 2; 8–9: 5; 9–10: 4; 1–6: 9; 2–7: 9; 3–8: 9; 4–9: 9; 5–10: 9; 2–9: 1
답
표준 풀이 (계산기 없이)
- S에서 Dijkstra를 적용합니다. u는 새로 확정한 정점, d(v)는 갱신된 임시 거리, ∞는 아직 도달 불가입니다.
- u=1, d(1)=0; d(2)=5, d(6)=9
- u=2, d(2)=5; d(3)=12, d(7)=14, d(9)=6
- u=9, d(9)=6; d(4)=15, d(8)=11, d(10)=10
- u=6, d(6)=9; d(5)=12
- u=10, d(10)=10; ∅
- 이전 정점을 역추적하고 경로 비용을 직접 더합니다: 1 → 2 → 9 → 10; 총비용 5+1+4=10
활용 상황
대학 수학 · 운용과학. 고정 네트워크에서 음이 아닌 가산 비용을 다룹니다. 도로 방향이나 실제 이동 조건을 자동 판단하지 않습니다.
네트워크 입력
- 첫 Y?에 S+Ti를 입력합니다. S는 출발점, T는 도착점입니다. 이후 Y?에 무방향 간선 a+bi, M?에 비용을 번갈아 입력합니다. i는 ENG이며 정점 수나 간선 수는 입력하지 않습니다.
- 끝낼 때 다음 Y?에서 EXE만, 이어지는 M?에서도 EXE만 누릅니다. 서로 다른 두 질문입니다. 알려진 비용 0은 0EXE로 입력합니다.
경로와 비용 읽기
- 각 Disp 화면은 S부터 시작하는 경로 정점 하나입니다. T를 포함한 모든 정점 뒤에 EXE를 누르면 마지막에 총비용이 나옵니다. −1은 경로 없음, S=T이면 S 다음 0입니다. 마지막에는 AC로 나갑니다. EXE는 재실행합니다.
조건과 제한
- 정점 번호는 정수 1–10, 간선 비용은 정수 0–100이며 자기 루프 이외의 간선을 최대 15개 저장합니다. 중복 간선도 각각 한 칸을 차지합니다. 비용 단위를 통일합니다.
- 15간선 버전은 정점 범위와 비용 정수 여부를 완전히 검사하지 않습니다. 지원 범위의 데이터만 입력합니다. 음수·누락 비용 또는 용량 초과는 Math ERROR입니다. 용량이 남으면 끝점 없이 음이 아닌 비용을 넣은 항목과 자기 루프는 무시합니다. 가득 차면 두 칸 공백 종료만 허용합니다.
- 공용 680 bytes 중 547 bytes를 사용하므로 다른 슬롯에 133 bytes가 남습니다. 매 실행 시 A, B, C, D, X, Y, M, Ans를 지우므로 먼저 필요한 값을 보관합니다.
- CMPLX, a+bi, Norm 1로 작성·실행합니다. 예제는 Deg와 P1입니다. 정상 종료하면 Norm 1로 복원됩니다. i는 두 정점 번호를 묶는 표기이며 허수 비용이 아닙니다.
- 방향 간선, 음수 가중치, 정점 10개 초과는 지원하지 않습니다. 동률 경로 중 하나만 반환하며 최소 간선 수는 보장하지 않습니다. 유한 정밀도 여유가 작으므로 코드를 그대로 입력합니다.
이용 권한 확인 중…