YEZAELP

o59_oct_c2_speedup

Jun 11th, 2021
640
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using lli = long long;
  5. const lli INF = 1e18;
  6. const int N = 8e4;
  7. const int M = 2e5;
  8. const int L = 10;
  9. const int Q = 8;
  10. using pi = pair <int, int>;
  11. using pil = pair <int, lli>;
  12. using pli = pair <lli, int>;
  13. using plii = pair <lli, pi>;
  14.  
  15. vector <pil> g[N+10];
  16. int n, m, l, q;
  17. lli p[Q+10];
  18.  
  19. int Room[L+10];
  20. bool isRoom[N+10];
  21. lli dis_rr[L+10][L+10], dis_rn[L+10][N+10];
  22. int vs_rn[L+10][N+10];
  23.  
  24. lli dis[N+10][Q+10];
  25. bool vs[N+10][Q+10];
  26.  
  27. void Setting(){
  28.     // ???
  29.     for(int i=1;i<=l;i++){
  30.         for(int j=1;j<=l;j++){
  31.             dis_rr[i][j] = INF;
  32.         }
  33.     }
  34.     for(int i=1;i<=l;i++){
  35.         for(int j=1;j<=n;j++){
  36.             dis_rn[i][j] = INF;
  37.         }
  38.     }
  39.     for(int i=1;i<=n;i++){
  40.         for(int j=0;j<=8;j++){
  41.             dis[i][j] = INF;
  42.         }
  43.     }
  44. }
  45.  
  46. int BS(int u){
  47.     int s = 1, e = l;
  48.     while(s <= e){
  49.         int mid = (s + e) / 2;
  50.         if(Room[mid] == u) return mid;
  51.         else if(Room[mid] > u) e = mid - 1;
  52.         else s = mid + 1;
  53.     }
  54. }
  55.  
  56. int main(){
  57.  
  58.     p[0] = 1;
  59.     for(int i=1;i<=Q;i++){
  60.         p[i] = (lli) p[i-1] * 2;
  61.     }
  62.  
  63.     scanf("%d%d%d%d", &n, &m, &l, &q);
  64.  
  65.     for(int i=1;i<=m;i++){
  66.         int u, v;
  67.         lli w;
  68.         scanf("%d%d%lld", &u, &v, &w);
  69.         g[u].push_back({v, w});
  70.     }
  71.  
  72.     for(int i=1;i<=l;i++){
  73.         scanf("%d", &Room[i]);
  74.         isRoom[ Room[i] ] = true;
  75.     }
  76.  
  77.     sort(Room+1, Room+l+1);
  78.  
  79.     Setting();
  80.  
  81.     for(int i=1;i<=l;i++){
  82.         priority_queue <pli, vector <pli>, greater <pli>> pq;
  83.         dis_rn[i][ Room[i] ] = 0;
  84.         dis_rr[i][i] = 0;
  85.         pq.push({ dis_rn[i][ Room[i] ] , Room[i] });
  86.         while(!pq.empty()){
  87.             lli d = pq.top().first;
  88.             int u = pq.top().second;
  89.             pq.pop();
  90.             if(vs_rn[i][u]) continue;
  91.             vs_rn[i][u] = true;
  92.             if(isRoom[u])
  93.                 dis_rr[i][BS(u)] = d;
  94.             for(auto vw: g[u]){
  95.                 int v = vw.first;
  96.                 lli w = vw.second;
  97.                 if(!vs_rn[i][v] and (lli) d + w < dis_rn[i][v]){
  98.                     dis_rn[i][v] = (lli) d + w;
  99.                     pq.push({ dis_rn[i][v] , v });
  100.                 }
  101.             }
  102.         }
  103.     }
  104.  
  105.     priority_queue <plii, vector <plii>, greater <plii>> pq;
  106.     if(isRoom[1] and q > 0){
  107.         dis[1][1] = 0;
  108.         pq.push({ dis[1][1] , {1, 1} });
  109.     }
  110.     else {
  111.         dis[1][0] = 0;
  112.         pq.push({ dis[1][0] , {1, 0} });
  113.     }
  114.     while(!pq.empty()){
  115.         lli d = pq.top().first;
  116.         int u = pq.top().second.first;
  117.         int k = pq.top().second.second;
  118.         pq.pop();
  119.         if(vs[u][k]) continue;
  120.         vs[u][k] = true;
  121.  
  122.         // printf("u %d d %lld k %d\n", u, d, k);
  123.  
  124.         if(u == n){
  125.             printf("%lld", d);
  126.             return 0;
  127.         }
  128.  
  129.         if(isRoom[u]){
  130.             int ui = BS(u);
  131.             /// u -> n
  132.             if(!vs[n][k] and (lli) d + (lli)dis_rn[ui][n]/p[k] < dis[n][k]){
  133.                 dis[n][k] = (lli) d + (lli)dis_rn[ui][n]/p[k];
  134.                 pq.push({ dis[n][k] , {n, k} });
  135.             }
  136.             /// room -> room -> ...
  137.             if(k + 1 <= q){
  138.                 for(int i=1;i<=l;i++){
  139.                     int v = Room[i];
  140.                     if(ui == i) continue;
  141.                     if(k + 1 <= q and !vs[v][k+1] and (lli) d + (lli)dis_rr[ui][i]/p[k] < dis[v][k+1]){
  142.                         dis[v][k+1] = (lli) d + (lli)dis_rr[ui][i]/p[k];
  143.                         pq.push({ dis[v][k+1], {v, k+1} });
  144.                     }
  145.                 }
  146.             }
  147.  
  148.         }
  149.         else {
  150.             for(auto vw: g[u]){
  151.                 int v = vw.first;
  152.                 lli w = vw.second;
  153.                 if(!isRoom[v] and !vs[v][k] and (lli) d + (lli)w/p[k] < dis[v][k]){
  154.                     dis[v][k] = (lli) d + (lli)w/p[k];
  155.                     pq.push({ dis[v][k] , {v, k} });
  156.                 }
  157.                 else if(isRoom[v] and k + 1 <= q and !vs[v][k+1] and (lli) d + (lli)w/p[k] < dis[v][k+1]){
  158.                     dis[v][k+1] = (lli) d + (lli)w/p[k];
  159.                     pq.push({ dis[v][k+1] , {v, k+1} });
  160.                 }
  161.             }
  162.         }
  163.     }
  164.  
  165.     return 0;
  166. }
  167.  
  168. /*
  169.  
  170. 4 4 1 2
  171. 1 2 256
  172. 2 4 2560
  173. 2 3 256
  174. 3 2 256
  175. 3
  176. 1920
  177.  
  178. 4 4 1 0
  179. 1 2 256
  180. 2 4 2560
  181. 2 3 256
  182. 3 2 256
  183. 1
  184.  
  185. */
  186.  
RAW Paste Data