Nội dung Bài tập
- Mã:
- FLOYD
- Tên:
- Tìm đường đi ngắn nhất 1
- Dạng thi:
- oi
- Thang điểm:
- 10 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Được tạo bởi:
- 4201103017
Cho đơn đồ thị có hướng với N đỉnh (0 < N < 1000). Hãy tìm đường đi ngắn nhất từ đỉnh u đến đỉnh v bất kỳ của đồ thị.
Yêu cầu: Sử dụng thuật toán Floyd để giải bài tập này.
Dữ liệu vào:
- Dòng 1: Nhập 3 số N u v
- N dòng tiếp theo: nhập ma trận trọng số của đồ thị
Dữ liệu ra:
- Nếu có đường đi thì xuất:
+ Tổng độ dài đường đi
+ Đường đi từ u đến v theo mẫu: u->...->v
- Nếu không có đường đi xuất “NO”
Ví dụ:
Input:
4 2 4
0 9 0 3
0 0 8 0
5 0 0 0
0 4 1 0
Output:
16
2->3->1->4
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
#include <bits/stdc++.h>using namespace std;//Tự cho là gồm 4 chữ số , vì đề bài k n...