Nội dung Bài tập
- Mã:
- DIJKSTRA_FORDBELLMAN
- Tên:
- Tìm đường đi ngắn nhất 2
- 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) có trọng số không âm. 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 Dijkstra hoặc Ford-Bellman để 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ừ v ngược về u theo mẫu: v<- ... <-u
- Nếu không có đường đi xuất “NO”
Ví dụ:
Input:
6 1 6
0 1 0 0 0 0
0 0 5 2 0 7
0 0 0 0 0 1
2 0 1 0 4 0
0 0 0 3 0 0
0 0 0 0 1 0
Output:
5
6<-3<-4<-2<-1
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 <iostream>using namespace std;struct ps { int tu, mau; &...