Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<cstring>
- #include<cstdio>
- #include<vector>
- #include<queue>
- ///#include<iostream>
- using namespace std;
- const int MAXN=1000001,MAXKi=1024;
- struct edge
- {
- int ver,p;
- edge(){ver=p=0;}
- edge(int _ver,int _p)
- {
- ver=_ver;
- p=_p;
- }
- bool operator<(const edge &e)const
- {
- return p>e.p;
- }
- };
- int n,U,D,I,J,l;
- bool used[MAXN];
- unsigned int d[MAXN];
- ///vector<edge>v[MAXN];
- vector<int>v[MAXN];
- int a[MAXKi];
- void init_v_second_version(int &sz)
- {
- /*edge e;
- e.p=I+J;
- for(int i=0;i<sz;i++)
- for(int j=i+1;j<sz;j++)
- {
- e.ver=a[j];
- v[a[i]].push_back(e);
- e.ver=a[i];
- v[a[j]].push_back(e);
- }*/
- for(int i=0;i<sz;i++)
- for(int j=0;j<sz;j++)
- {
- v[a[i]].push_back(a[j]);
- v[a[j]].push_back(a[i]);
- }
- }
- void read()
- {
- scanf("%d%d%d%d%d%d",&n,&U,&D,&I,&J,&l);
- int sz;
- for(int i=0;i<l;i++)
- {
- scanf("%d",&sz);
- for(int j=0;j<sz;j++)
- scanf("%d",&a[j]);
- init_v_second_version(sz);
- }
- }
- void solve()
- {
- priority_queue<edge>q;
- edge e(1,0),w,nb;
- int sz,price=I+J;
- q.push(e);
- memset(d,-1,sizeof(d));
- d[1]=0;
- while(!q.empty())
- {
- e=q.top();q.pop();
- if(e.p<=d[e.ver])
- {
- if(!used[e.ver])
- {
- used[e.ver]=true;
- sz=v[e.ver].size();
- for(int i=0;i<sz;i++)
- {
- nb.ver=v[e.ver][i];
- nb.p=price;
- if(nb.p+e.p<d[nb.ver])
- {
- d[nb.ver]=nb.p+e.p;
- nb.p+=e.p;
- q.push(nb);
- }
- }
- nb.ver=e.ver+1;
- nb.p=U;
- if(nb.p+e.p<d[nb.ver])
- {
- d[nb.ver]=nb.p+e.p;
- nb.p+=e.p;
- q.push(nb);
- }
- nb.ver=e.ver-1;
- nb.p=D;
- if(nb.p+e.p<d[nb.ver])
- {
- nb.p+=e.p;
- d[nb.ver]=nb.p;
- q.push(nb);
- }
- }
- }
- }
- printf("%d\n",d[n]);
- }
- int main()
- {
- read();
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement