HSG THPT TPHCM 2022 - Đề xuất
Xem dạng PDF
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
4 5 3 1 4
1 2 13
2 3 10
3 1 15
3 4 16
4 1 18
1 3 21
2 3 5
2 4 20
Sample Output 1
33
Bình luận
Đăng bình luận không xóa được hả mọi người? Quá chán
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
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; }
Đề bài ghi
nhưng vẫn phải xét đến phương án không chọn con đường mới nào
/