Advertisement
STEFAN_STOYANOV

1087

Mar 28th, 2021
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.38 KB | None | 0 0
  1. #include<cstring>
  2. #include<cstdio>
  3. #include<vector>
  4. #include<queue>
  5. ///#include<iostream>
  6. using namespace std;
  7. const int MAXN=1000001,MAXKi=1024;
  8. struct edge
  9. {
  10.     int ver,p;
  11.     edge(){ver=p=0;}
  12.     edge(int _ver,int _p)
  13.     {
  14.         ver=_ver;
  15.         p=_p;
  16.     }
  17.     bool operator<(const edge &e)const
  18.     {
  19.         return p>e.p;
  20.     }
  21. };
  22. int n,U,D,I,J,l;
  23. bool used[MAXN];
  24. unsigned int d[MAXN];
  25. ///vector<edge>v[MAXN];
  26. vector<int>v[MAXN];
  27. int a[MAXKi];
  28. void init_v_second_version(int &sz)
  29. {
  30.     /*edge e;
  31.     e.p=I+J;
  32.     for(int i=0;i<sz;i++)
  33.         for(int j=i+1;j<sz;j++)
  34.     {
  35.         e.ver=a[j];
  36.         v[a[i]].push_back(e);
  37.         e.ver=a[i];
  38.         v[a[j]].push_back(e);
  39.     }*/
  40.     for(int i=0;i<sz;i++)
  41.         for(int j=0;j<sz;j++)
  42.     {
  43.         v[a[i]].push_back(a[j]);
  44.         v[a[j]].push_back(a[i]);
  45.     }
  46. }
  47. void read()
  48. {
  49.     scanf("%d%d%d%d%d%d",&n,&U,&D,&I,&J,&l);
  50.     int sz;
  51.     for(int i=0;i<l;i++)
  52.     {
  53.         scanf("%d",&sz);
  54.         for(int j=0;j<sz;j++)
  55.             scanf("%d",&a[j]);
  56.         init_v_second_version(sz);
  57.     }
  58. }
  59. void solve()
  60. {
  61.     priority_queue<edge>q;
  62.     edge e(1,0),w,nb;
  63.     int sz,price=I+J;
  64.     q.push(e);
  65.     memset(d,-1,sizeof(d));
  66.     d[1]=0;
  67.     while(!q.empty())
  68.     {
  69.         e=q.top();q.pop();
  70.         if(e.p<=d[e.ver])
  71.         {
  72.             if(!used[e.ver])
  73.             {
  74.                 used[e.ver]=true;
  75.                 sz=v[e.ver].size();
  76.                 for(int i=0;i<sz;i++)
  77.                 {
  78.                     nb.ver=v[e.ver][i];
  79.                     nb.p=price;
  80.                     if(nb.p+e.p<d[nb.ver])
  81.                     {
  82.                         d[nb.ver]=nb.p+e.p;
  83.                         nb.p+=e.p;
  84.                         q.push(nb);
  85.                     }
  86.                 }
  87.                 nb.ver=e.ver+1;
  88.                 nb.p=U;
  89.                 if(nb.p+e.p<d[nb.ver])
  90.                 {
  91.                     d[nb.ver]=nb.p+e.p;
  92.                     nb.p+=e.p;
  93.                     q.push(nb);
  94.                 }
  95.                 nb.ver=e.ver-1;
  96.                 nb.p=D;
  97.                 if(nb.p+e.p<d[nb.ver])
  98.                 {
  99.                     nb.p+=e.p;
  100.                     d[nb.ver]=nb.p;
  101.                     q.push(nb);
  102.                 }
  103.             }
  104.         }
  105.     }
  106.     printf("%d\n",d[n]);
  107. }
  108. int main()
  109. {
  110.     read();
  111.     solve();
  112.     return 0;
  113. }
  114.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement