Giúp mình bài toán đồ thị:

[romanov]

Cho một đồ thị vô hướng với N (N là số chẵn) đỉnh và M cạnh, giữa 2 đỉnh có thể có đường nối với trọng số L (L<=10000, nếu có thì tối đa chỉ 1 đường trực tiếp giữa 2 đỉnh). Từ 2 đỉnh bất kỳ P,Q khác nhau, hãy tìm 2 đường đi, mỗi đường đi qua N/2 điểm khác nhau sao cho tổng trọng số của mỗi đường đi là nhỏ nhất. P,Q đều chưa xác định và cũng phải tìm (Lưu ý là những đỉnh đã thuộc đường đi 1 đều không được có trong đường đi 2, luôn tồn tại ít nhất một đáp án.). Dữ liệu vào:
_Dòng đầu tiên là 2 số N,M
_M dòng tiếp theo, mỗi dòng ghi 3 số là A,B,L nghĩa là có đường nối từ đỉnh A đến đỉnh B có trọng số L.
Kết quả xuất ra:
-Dòng đầu tiên là các đỉnh thuộc đường đi thứ nhất.
-Dòng thứ 2 là các đỉnh thuộc đường đi thứ 2.
(Mỗi dòng đều phải có N/2 đỉnh).
VD:
Graph.inp
6 8
1 2 5
1 4 8
1 6 7
2 3 6
3 4 5
3 6 2
4 5 3
5 6 2
Graph.out
1 4 5
2 3 6

Thank các bạn rất nhiều

[HGMinh95]

Tổng trọng số của mỗi đường đi là nhỏ nhất nghĩa là thế nào hả bạn???
Ví dụ có 2 cách:
C1: Đường đi 1: 7 Đường đi 2: 8
C2: Đường đi 1: 3 Đường đi 2: 12
thì chọn cách nào?

[romanov]

Nghĩa là:
-đường số 1 đi qua các đỉnh 1->4->5 có tổng trọng số 8+3=11
-đường số 2 đi qua các đỉnh 2->3->6 có tổng trọng số 6+2=8
đây là 2 đường ngắn nhất(trọng số nhỏ nhất) thỏa mãn đề: mỗi đường đi qua N/2 đỉnh.

[HGMinh95]

Mình vẫn không hiểu lắm :)
Đường 1: 1->2->3 tổng trọng số 5+6=11
Đường 2: 4->5->6 tổng trọng số 2+3=5
Cách này còn ngắn hơn cả cách nêu trong ví dụ mà vẫn t/m đề bài.