fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int MAXN = 1005;
  5. const int MAXT = 100005;
  6. const ll INF = 1e18;
  7.  
  8. int n, m, s, t;
  9. int st, en;
  10. vector<pair<int, int>> adj[MAXN];
  11. ll dist[MAXN][MAXN]; // dist[i][j]: khoảng cách từ i đến j
  12. ll price[MAXN];      // giá xăng rẻ nhất tại thành phố i
  13. vector<int> important; // danh sách các đỉnh quan trọng
  14. int idx_map[MAXN];   // ánh xạ id đỉnh gốc -> index trong important
  15.  
  16. void dijkstra(int start, ll d[]) {
  17.     for (int i = 1; i <= n; i++) d[i] = INF;
  18.     d[start] = 0;
  19.     priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
  20.     pq.push({0, start});
  21.     while (!pq.empty()) {
  22.         int u = pq.top().second;
  23.         ll cur_d = pq.top().first;
  24.         pq.pop();
  25.         if (cur_d != d[u]) continue;
  26.         for (auto &e : adj[u]) {
  27.             int v = e.first, w = e.second;
  28.             if (d[v] > d[u] + w) {
  29.                 d[v] = d[u] + w;
  30.                 pq.push({d[v], v});
  31.             }
  32.         }
  33.     }
  34. }
  35.  
  36. int main() {
  37.     ios_base::sync_with_stdio(false);
  38.     cin.tie(0);
  39.  
  40.     // Đọc input
  41.     cin >> n >> m >> s;
  42.     cin >> t;
  43.     for (int i = 0; i < m; i++) {
  44.         int u, v, w;
  45.         cin >> u >> v >> w;
  46.         adj[u].push_back({v, w});
  47.         adj[v].push_back({u, w});
  48.     }
  49.     for (int i = 1; i <= n; i++) price[i] = INF;
  50.     for (int i = 0; i < s; i++) {
  51.         int p, c;
  52.         cin >> p >> c;
  53.         price[p] = min(price[p], (ll)c);
  54.     }
  55.     cin >> st >> en;
  56.  
  57.     // Thêm các đỉnh quan trọng: có trạm xăng hoặc st, en
  58.     set<int> imp_set;
  59.     for (int i = 1; i <= n; i++) {
  60.         if (price[i] != INF) imp_set.insert(i);
  61.     }
  62.     imp_set.insert(st);
  63.     imp_set.insert(en);
  64.     important = vector<int>(imp_set.begin(), imp_set.end());
  65.     int k = important.size();
  66.     for (int i = 0; i < k; i++) {
  67.         idx_map[important[i]] = i;
  68.     }
  69.  
  70.     // Tính khoảng cách giữa các đỉnh quan trọng
  71.     for (int i = 0; i < k; i++) {
  72.         int u = important[i];
  73.         dijkstra(u, dist[u]);
  74.     }
  75.  
  76.     // Khởi tạo dp: [id trong important][lượng xăng]
  77.     vector<vector<ll>> dp(k, vector<ll>(t+1, INF));
  78.     int st_idx = idx_map[st];
  79.     for (int f = 0; f <= t; f++) {
  80.         dp[st_idx][f] = price[st] * f;
  81.     }
  82.  
  83.     // Dijkstra trên state (i, f)
  84.     using state = tuple<ll, int, int>; // (cost, id, fuel)
  85.     priority_queue<state, vector<state>, greater<state>> pq;
  86.     for (int f = 0; f <= t; f++) {
  87.         if (dp[st_idx][f] < INF) {
  88.             pq.push({dp[st_idx][f], st_idx, f});
  89.         }
  90.     }
  91.  
  92.     while (!pq.empty()) {
  93.         auto [cost, i, f] = pq.top();
  94.         pq.pop();
  95.         if (cost != dp[i][f]) continue;
  96.         int u = important[i];
  97.  
  98.         // Mua thêm 1 lít
  99.         if (f < t) {
  100.             ll new_cost = cost + price[u];
  101.             if (new_cost < dp[i][f+1]) {
  102.                 dp[i][f+1] = new_cost;
  103.                 pq.push({new_cost, i, f+1});
  104.             }
  105.         }
  106.  
  107.         // Di chuyển đến đỉnh quan trọng khác
  108.         for (int j = 0; j < k; j++) {
  109.             if (i == j) continue;
  110.             int v = important[j];
  111.             ll d = dist[u][v];
  112.             if (d > t) continue; // không thể đi thẳng
  113.             if (f < d) continue; // không đủ xăng
  114.             int new_f = f - d;
  115.             if (dp[j][new_f] > cost) {
  116.                 dp[j][new_f] = cost;
  117.                 pq.push({cost, j, new_f});
  118.             }
  119.         }
  120.     }
  121.  
  122.     // Kết quả
  123.     int en_idx = idx_map[en];
  124.     ll ans = INF;
  125.     for (int f = 0; f <= t; f++) {
  126.         ans = min(ans, dp[en_idx][f]);
  127.     }
  128.     cout << ans << endl;
  129.  
  130.     return 0;
  131. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
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
stdout
copy 
1340
https://ideone.com/cRSVqP
language:
C++14 (clang 8.0)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!