

Đổ Xăng
`C++`
Vương quốc VNOI gồm `n` thành phố được liên kết với nhau bằng `m` con đường hai chiều, đảm bảo rằng mọi cặp thành phố đều có đường đi trực tiếp hoặc gián tiếp tới nhau. Con đường thứ `i` kết nối hai thành phố `u_i, v_i` và sẽ tổn `w_i` lít xăng để đi qua.
Là một người đam mê du lịch, bạn lên kế hoạch cho chuyến đi chơi của mình tới VNOI. Bạn xuất phát từ thành phố `st` và có dự định đi tới thành phố `en` bằng xe của mình. Tất nhiên đi xe thì phải tổn nhiên liệu, và xe của bạn có một bình xăng chứa được tối đa `t` lít xăng.
VNOI có `s` trạm xăng. Trạm xăng thứ `i` được phân bố ở thành phố `p_i` và có chi phí cho mỗi lít xăng là `c_i`. Ở mỗi trạm xăng, bạn có thể mua không giới hạn số xăng (tất nhiên xe bạn chỉ mang tối đa được `t` lít xăng thôi).
Bạn bắt đầu từ thành phố `st` và xe bạn ban đầu không có xăng - may mắn rằng đảm bảo luôn có trạm xăng ở thành phố nơi bạn xuất phát. Hãy tính số tiền ít nhất cần bỏ ra để hoàn thành hành trình từ `st` tới `en`.
Input
Dòng đầu gồm 3 số nguyên dương `n, m, s (2 <= n <= 1000; 1 <= m <= 10^4; 1 <= s <= 100)`
Dòng tiếp theo gồm một số nguyên dương `t (1 <= t <= 10^5)` mô tả sức chứa của bình xăng.
`m` dòng tiếp theo, dòng thứ `i` gồm ba số nguyên dương `u_i, v_i, w_i (1 <= u_i, v_i <= n; 1 <= w_i <= t)` miêu tả con đường thứ `i`.
`s` dòng tiếp theo, dòng thứ `i` gồm hai số nguyên dương `p_i, q_i (1 <= p_i <= n; 1 <= q_i <= 100)` miêu tả trạm xăng thứ `i`.
Dòng cuối cùng gồm hai số nguyên dương `st, en (1 <= st, en <= n)` miêu tả vị trí ban đầu và đích đến của bạn.
Output
In ra số tiền ít nhất cần để đi chuyến.
Sample Input 1
3 3 2
200
1 3 80
1 2 50
2 3 50
1 70
2 40
1 3
Sample Output 1
5500
Sample Input 2
5 5 3
100
1 2 80
2 5 80
1 3 40
3 4 60
4 5 60
1 8
2 9
3 2
1 5
Sample Output 2
1340
Sample Input 3
4 3 3
10
1 2 2
2 3 6
3 4 3
1 4
2 7
3 9
2 4
Sample Output 3
61
Hãy luôn nhớ cảm ơn và vote 5*
nếu câu trả lời hữu ích nhé!
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
const int INF = 1e9;
const ll INF_LL = 1e18;
int n, m, num_s, max_t, st, en, K, nodes[105], id_st, id_en;
int d1[105][1005];
ll c[1005], f[105];
vector<pii> g1[1005];
vector<pli> g2[105];
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
if (!(cin >> n >> m >> num_s)) return 0;
cin >> max_t;
REP(i, m) {
int u, v, w; cin >> u >> v >> w;
g1[u].pb({v, w}); g1[v].pb({u, w});
}
FOR(i, 1, n) c[i] = INF_LL;
REP(i, num_s) {
int p; ll q; cin >> p >> q;
c[p] = min(c[p], q);
}
cin >> st >> en;
FOR(i, 1, n) if (c[i] != INF_LL || i == st || i == en) nodes[K++] = i;
REP(i, K) {
int start = nodes[i];
FOR(j, 1, n) d1[i][j] = INF;
priority_queue<pii, vector<pii>, greater<pii>> pq;
d1[i][start] = 0; pq.push({0, start});
while (!pq.empty()) {
auto [u_d, u] = pq.top(); pq.pop();
if (u_d > d1[i][u]) continue;
for (auto& edge : g1[u]) {
int v = edge.fi, w = edge.se;
if (d1[i][u] + w < d1[i][v]) {
d1[i][v] = d1[i][u] + w;
pq.push({d1[i][v], v});
}
}
}
}
REP(i, K) {
int u = nodes[i]; if (c[u] == INF_LL) continue;
REP(j, K) {
int v = nodes[j];
if (u != v && d1[i][v] <= max_t) g2[i].pb({j, 1LL * d1[i][v] * c[u]});
}
}
id_st = -1, id_en = -1;
REP(i, K) {
if (nodes[i] == st) id_st = i;
if (nodes[i] == en) id_en = i;
}
REP(i, K) f[i] = INF_LL;
priority_queue<pli, vector<pli>, greater<pli>> pq;
f[id_st] = 0; pq.push({0, id_st});
while (!pq.empty()) {
auto [u_d, u] = pq.top(); pq.pop();
if (u_d > f[u]) continue;
if (u == id_en) break;
for (auto& edge : g2[u]) {
int v = edge.fi; ll w = edge.se;
if (f[u] + w < f[v]) {
f[v] = f[u] + w; pq.push({f[v], v});
}
}
}
cout << f[id_en] << "\n";
return 0;
}
Hãy giúp mọi người biết câu trả lời này thế nào?

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
ll n,m,s,t;
cin>>n>>m>>s>>t;
vector<pair<ll,ll>> a[1005];
for(ll i=1;i<=m;i++){
ll tam1,tam2,tam3;
cin>>tam1>>tam2>>tam3;
a[tam1].push_back({tam2,tam3});
a[tam2].push_back({tam1,tam3});
}
ll b[1005];
for(ll i=1;i<=n;i++)
b[i]=101;
for(ll i=1;i<=s;i++){
ll res1,res2;
cin>>res1>>res2;
b[res1]=min(b[res1],res2);
}
ll st,en;
cin>>st>>en;
const ll max=1e18;
vector<vector<ll>> c(n+1,vector<ll>(n+1,max));
for(ll i=1;i<=n;i++){
priority_queue<pair<ll,ll>,
vector<pair<ll,ll>>,
greater<pair<ll,ll>>> d;
c[i][i]=0;
d.push({0,i});
while(!d.empty()){
auto [res3,tam1]=d.top();
d.pop();
if(res3!=c[i][tam1])
continue;
for(auto [tam2,tam3]:a[tam1]){
if(c[i][tam2]>res3+tam3){
c[i][tam2]=res3+tam3;
d.push({c[i][tam2],tam2});
}
}
}
}
vector<ll> f(n+1,max);
priority_queue<pair<ll,ll>,
vector<pair<ll,ll>>,
greater<pair<ll,ll>>> d;
f[st]=0;
d.push({0,st});
while(!d.empty()){
auto [res3,tam1]=d.top();
d.pop();
if(res3!=f[tam1])
continue;
for(ll tam2=1;tam2<=n;tam2++){
if(c[tam1][tam2]<=t&&b[tam1]!=101){
ll res4=res3+c[tam1][tam2]*b[tam1];
if(res4<f[tam2]){
f[tam2]=res4;
d.push({res4,tam2});
}
}
}
}
cout<<f[en];
}
Hãy giúp mọi người biết câu trả lời này thế nào?
Bảng tin