fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. const ll LINF = (ll)9e18;
  5.  
  6. struct Edge {
  7.     int to;
  8.     int w;
  9. };
  10.  
  11. struct DEdge {
  12.     int from, to;
  13.     ll w;
  14.     bool covered;
  15.     DEdge(int _f=0,int _t=0,ll _w=0):from(_f),to(_t),w(_w),covered(false){}
  16. };
  17.  
  18. int main(){
  19.     ios::sync_with_stdio(false);
  20.     cin.tie(nullptr);
  21.  
  22.     int N, M, K;
  23.     if(!(cin >> N >> M >> K)) return 0;
  24.     vector<int> U(M), V(M);
  25.     vector<int> W(M);
  26.     vector<vector<Edge>> g(N+1);
  27.     for(int i=0;i<M;i++){
  28.         int u,v; int w;
  29.         cin >> u >> v >> w;
  30.         U[i]=u; V[i]=v; W[i]=w;
  31.         g[u].push_back({v,w});
  32.         g[v].push_back({u,w});
  33.     }
  34.     // data for K people: index 1 is Nam
  35.     vector<int> a(K+1), b(K+1), p(K+1, 1); // p unused for Nam
  36.     cin >> a[1] >> b[1];
  37.     for(int i=2;i<=K;i++){
  38.         int pi, ai, bi;
  39.         cin >> pi >> ai >> bi;
  40.         p[i] = pi; a[i] = ai; b[i] = bi;
  41.     }
  42.  
  43.     auto dijkstra = [&](int src)->vector<ll>{
  44.         vector<ll> dist(N+1, LINF);
  45.         priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
  46.         dist[src]=0;
  47.         pq.push({0, src});
  48.         while(!pq.empty()){
  49.             auto cur = pq.top(); pq.pop();
  50.             ll d = cur.first;
  51.             int u = cur.second;
  52.             if(d != dist[u]) continue;
  53.             for(const Edge &e : g[u]){
  54.                 int v = e.to; ll nd = d + e.w;
  55.                 if(nd < dist[v]){
  56.                     dist[v] = nd;
  57.                     pq.push({nd, v});
  58.                 }
  59.             }
  60.         }
  61.         return dist;
  62.     };
  63.  
  64.     // Dijkstra cho Nam: từ a1 và từ b1
  65.     vector<ll> distA1 = dijkstra(a[1]);
  66.     vector<ll> distB1 = dijkstra(b[1]);
  67.     ll D = distA1[b[1]];
  68.     if(D>=LINF){
  69.         // không có đường từ a1 tới b1 (không hợp lý theo đề nhưng phòng hờ)
  70.         cout << 0 << "\n";
  71.         return 0;
  72.     }
  73.  
  74.     // Xây DAG gồm các cạnh (u->v) nằm trên một đường ngắn nhất từ a1 đến b1
  75.     vector<DEdge> dedges;
  76.     dedges.reserve(2*M);
  77.     vector<vector<int>> dagAdj(N+1); // lưu indices của dedges
  78.     for(int i=0;i<M;i++){
  79.         int u = U[i], v = V[i]; ll w = W[i];
  80.         // hướng u -> v
  81.         if(distA1[u] < LINF && distA1[v] < LINF && distA1[u] + w == distA1[v]){
  82.             if(distA1[v] + distB1[v] == D){
  83.                 dedges.emplace_back(u, v, w);
  84.                 dagAdj[u].push_back((int)dedges.size()-1);
  85.             }
  86.         }
  87.         // hướng v -> u
  88.         if(distA1[v] < LINF && distA1[u] < LINF && distA1[v] + w == distA1[u]){
  89.             if(distA1[u] + distB1[u] == D){
  90.                 dedges.emplace_back(v, u, w);
  91.                 dagAdj[v].push_back((int)dedges.size()-1);
  92.             }
  93.         }
  94.     }
  95.  
  96.     // Với mỗi bạn (ngoại trừ Nam), chạy Dijkstra từ a_i và b_i, đánh dấu các directed-edge nào
  97.     // nằm trên một đường ngắn nhất của bạn đó; nếu bạn dễ tính p=1 -> luôn có thể thay đổi thời gian;
  98.     // nếu khó tính p=0 -> cần distAi[u] == distA1[u] để gặp tại bắt đầu cạnh.
  99.     for(int i=2;i<=K;i++){
  100.         vector<ll> distAi = dijkstra(a[i]);
  101.         vector<ll> distBi = dijkstra(b[i]);
  102.         ll Di = distAi[b[i]];
  103.         if(Di >= LINF) continue; // bạn này không có đường hợp lệ
  104.  
  105.         // duyệt các directed edges
  106.         for(size_t idx=0; idx<dedges.size(); ++idx){
  107.             if(dedges[idx].covered) continue; // đã có ai cover thì khỏi kiểm tra
  108.             int u = dedges[idx].from, v = dedges[idx].to;
  109.             ll w = dedges[idx].w;
  110.             // cần kiểm tra cạnh có thuộc đường ngắn nhất của bạn i
  111.             if(distAi[u] < LINF && distAi[v] < LINF && distAi[u] + w == distAi[v] && distAi[v] + distBi[v] == Di){
  112.                 if(p[i] == 1){
  113.                     dedges[idx].covered = true;
  114.                 }else{
  115.                     // khó tính: bắt đầu điểm u phải đến đúng lúc như Nam
  116.                     if(distAi[u] == distA1[u]){
  117.                         dedges[idx].covered = true;
  118.                     }
  119.                 }
  120.             }
  121.         }
  122.     }
  123.  
  124.     // DP tìm đường (a1 -> b1) trên DAG maximize tổng w của các cạnh được covered
  125.     // Sắp xếp các đỉnh theo distA1 tăng dần (đây là topological order trên DAG)
  126.     vector<int> order(N);
  127.     for(int i=0;i<N;i++) order[i] = i+1;
  128.     sort(order.begin(), order.end(), [&](int x, int y){
  129.         if(distA1[x] != distA1[y]) return distA1[x] < distA1[y];
  130.         return x < y;
  131.     });
  132.  
  133.     vector<ll> dp(N+1, -LINF);
  134.     dp[a[1]] = 0;
  135.     for(int u : order){
  136.         if(dp[u] == -LINF) continue;
  137.         // duyệt các cạnh u -> v
  138.         for(int idx : dagAdj[u]){
  139.             int v = dedges[idx].to;
  140.             ll add = dedges[idx].covered ? dedges[idx].w : 0LL;
  141.             if(dp[u] + add > dp[v]){
  142.                 dp[v] = dp[u] + add;
  143.             }
  144.         }
  145.     }
  146.  
  147.     ll ans = dp[b[1]];
  148.     if(ans < 0) ans = 0; // phòng hờ
  149.     cout << ans << "\n";
  150.     return 0;
  151. }
  152.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Uyu1sh
language:
C++14 (gcc 8.3)
created:
22 hours 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!