HSG THPT TPHCM 2022 - Đề xuất - VNOJ: VNOI Online Judge

HSG THPT TPHCM 2022 - Đề xuất

Điểm: 0,15 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Tác giả:

bedao

Nguồn bài:

Kỳ thi Học sinh giỏi THPT TPHCM 2022

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Mạng lưới giao thông thành phố gồm ~N~ nút được đánh số từ ~1~ đến ~N~ và ~M~ đường một chiều nối các cặp nút. Với ý định muốn giảm được độ dài của đường đi ngắn nhất từ nút trọng yếu ~S~ đến nút ~T~ ~(S \neq T)~, một danh sách gồm ~K~ đường hai chiều được đề xuất để xem xét xây dựng.

Yêu cầu: Viết một chương trình để chọn ra một đường trong danh sách đề xuất trên để xây dựng sao cho độ dài đường đi ngắn nhất từ ~S~ đến ~T~ là nhỏ nhất có thể.

Input

Dòng đầu tiên chứa năm số nguyên dương ~N~ ~(N \le 10^4)~, ~M~ ~(M \le 10^5)~, ~K~ ~(K \lt 300)~, ~S~ ~(S \le N)~, ~T~ ~(T \le N)~.
Trên ~M~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên dương ~A_i~, ~B_i~, ~L_i~. Trong đó ~L_i~ là độ dài của đường một chiều thứ ~i~ từ nút ~A_i~ đến nút ~B_i~ ~(L_i \le 1000)~.
Trên ~K~ dòng tiếp theo, dòng thứ ~j~ chứa ba số nguyên dương ~U_j~, ~V_j~, ~Q_j~. Trong đó ~Q_j~ là độ dài của đường hai chiều được đề xuất thứ ~j~ nối giữa hai nút ~U_j~ và ~V_j~ ~(Q_j \le 1000)~.

Các số trên một dòng cách nhau bởi ít nhất một dấu khoảng trắng.

Output

In độ dài nhỏ nhất có thể của đường đi ngắn nhất từ ~S~ đến ~T~ sau khi xây dựng xong một con đường hai chiều từ danh sách đề xuất. Trường hợp không có đường đi từ ~S~ đến ~T~ thì in ~-1~.

Sample Input 1

Sample Output 1

Bình luận

Hãy đọc nội quy trước khi bình luận.

-10

phongnq424 đã bình luận lúc 29, Tháng 3, 2024, 14:35

Đăng bình luận không xóa được hả mọi người? Quá chán

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-13

phongnq424 đã bình luận lúc 28, Tháng 3, 2024, 15:21

Code này của em bị lỗi gì á mọi người em không nhìn ra ớ, em bị wrong answer 20 test!

include<bits/stdc++.h>

using namespace std; typedef pair<int,int> ip;

define Max 2000000000

map<int, int> a[20005], b[20005]; int d[20005], t[20005]; bool visited[20005]; priority_queue<ip open>
void dijkfrom(int k) { visited[k] = true; open.pop(); map<int,int>:: iterator it; for (it=a[k].begin(); it!=a[k].end(); it++) if (!visited[it->first]) { if (d[k]+it->second<d[it->first]) d[it->first] = d[k] + it->second, open.push(makepair(d[it->first],it->first)); } if (!open.empty()) dijk_from(open.top().second); }

void dijkto(int k) { visited[k] = false; open.pop(); map<int,int>:: iterator it; for (it=b[k].begin(); it!=b[k].end(); it++) if (visited[it->first]) { if (t[k]+it->second<t[it->first]) t[it->first] = t[k] + it->second, open.push(makepair(t[it->first],it->first)); } if (!open.empty()) dijk_to(open.top().second); }

int main() { int n, m, k, u, v, q, di, den; cin >> n >> m >> k >> di >> den; for (int i=1; i<=m; i++) { cin >> u >> v >> q; a[u][v] = q; b[v][u] = q; } for (int i=1; i<=n; i++) d[i] = Max, visited[i] = false; d[di] = 0; open.push(makepair(0,di)); dijkfrom(di); //cout << "Duong di tu di -> den: " << d[den] << "\n"; for (int i=1; i<=n; i++) t[i] = Max; t[den] = 0; open.push(makepair(0,den)); dijkto(den); int res = d[den]; for (int i=1; i<=k; i++) cin >> u >> v >> q, res = min(res,min(d[u]+t[v]+q,d[v]+t[u]+q)); if (res>=Max) cout << -1; else cout << res; }
</ip>

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

16

Vhai05 đã bình luận lúc 13, Tháng 1, 2024, 17:14

Đề bài ghi

Yêu cầu: Viết một chương trình để chọn ra một đường trong danh sách đề xuất trên để xây dựng sao cho độ dài đường đi ngắn nhất từ S đến T là nhỏ nhất có thể.

nhưng vẫn phải xét đến phương án không chọn con đường mới nào

-13

yuyuuend đã bình luận lúc 7, Tháng 1, 2024, 1:09 ← chỉnh sửa →

/

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.