小A最近喜欢上一款游戏：游戏把地图分了一些区域，这些区域可能会重叠，也可能不会。

游戏中有一项传送技能，改传送技能只能将在同一区域的两个地方使用。小A可以利用区域中重叠部分来实现从某一区域到另一个区域的移动。

当然技能会消耗魔法值，对于同一区域内两点，消耗的魔法值是相同的。如下图：

有红蓝两个区域，共4个地点1 2 3 4，假设在红色区域移动只需消耗a1点魔法值，在蓝色区域间移动需花费a2点魔法值，那么1和2之间或者1和3之间都需花费a1点魔法，2和4或者3和4之间都需要a2点魔法，2和3之间选择消耗a1点魔法也可以选择消耗a2点魔法。

现在小A在S点接到了一个任务，需要到达F点去做任务，再到P点交任务。

现在让你求一下完成该任务，需要因为传送消耗的魔法值至少为多少。

当然有些地方需要花RMB才能到达，即你从S点无论如何也无法到达F点去做任务，或者F点无法到达P点。因为双11，小A已经没有RMB了，这是你只需告诉他“Poor guy, you don’t have enough Money!”。

多组样例输入（不会超过10组）

对于每一组样例：

第一行有五个整数 n m S F P 表示有n个地点和m个区域(2<=n<=100000)    (0<m<1000000)。S F P为题目中所述的地点编号。（地点编号为：1,2,3......,n）.

接下来每行描述的是每一个区域的信息，

ai bi 表示 在第i块区域内需要消耗ai点魔法值，第i各区域有bi个地点，然后有bi个数，代表第i个区域内第地点编号。(1<=ai<=1000000000, bi>0) .

保证所有bi的和小于1000000.

如果无解，则输出“Poor guy, you don’t have enough Money!”（引号中的内容）。

否则就输出最少的消耗的魔法量。

 #include<iostream>

 #include<cstdio>

 #include<queue>

 #include<cstring>

 const int maxl=;

 const int maxn=;

 using namespace std;

 int n,m,s,t,p;

 int lin[maxn],cnt=;

 struct str

 {

     int y;

     int z;

     int next;

 }e[maxl];

 void insert(int x,int y,int z)

 {

     cnt++;

     e[cnt].next=lin[x];

     lin[x]=cnt;

     e[cnt].y=y;

     e[cnt].z=z;

 }

 struct strdis

 {

     int x;

     long long dis;

     bool operator<(const strdis& a)const{return dis<a.dis;}

     void set(int xx,int diss){x=xx;dis=diss;}

 }temp,noww;

 //bool operator <(const strdis &a,const strdis &b){return a.dis<b.dis;}

 priority_queue <strdis> q;

 bool vis[maxn];

 long long dis[maxn];

 int main()

 {

     while(scanf("%d%d%d%d%d",&n,&m,&s,&p,&t)!=EOF)

     {

         memset(lin,,sizeof(lin));cnt=;

         memset(vis,,sizeof(vis));

         for(int i=;i<=m;i++)

         {

             int ai,bi,x;

             scanf("%d%d",&ai,&bi);

             for(int j=;j<=bi;j++)

             {

                 scanf("%d",&x);

                 insert(x,n+i,ai);

                 insert(n+i,x,);

             }

         }

         temp.set(p,);

         q.push(temp);

         memset(dis,0x3f,sizeof(dis));

         dis[p]=;

         while(!q.empty())

         {

             noww=q.top();

             q.pop();

             int nn=noww.x;

             if(vis[nn])continue;

             vis[nn]=;

             for(int i=lin[nn];i;i=e[i].next)

             {

                 int u=e[i].y;

                 if(dis[u]>dis[nn]+e[i].z)

                 {

                     dis[u]=dis[nn]+e[i].z;

                     temp.set(u,dis[u]);

                     q.push(temp);

                 }

             }

         }

         if((!vis[s])||(!vis[t]))

         {

             printf("Poor guy, you don't have enough Money!\n");

         }

         else

         {

             printf("%lld\n",dis[s]+dis[t]);

         }

     }

     return ;

 }

Dijkstra

 #include<iostream>

 #include<cstdio>

 #include<queue>

 #include<cstring>

 const int maxl=;

 const int maxn=;

 using namespace std;

 int n,m,s,t,p;

 int lin[maxn],cnt=;

 struct str

 {

     int y;

     int z;

     int next;

 }e[maxl];

 void insert(int x,int y,int z)

 {

     cnt++;

     e[cnt].next=lin[x];

     lin[x]=cnt;

     e[cnt].y=y;

     e[cnt].z=z;

 }

 struct strdis

 {

     int x;

     long long dis;

     bool operator<(const strdis& a)const{return dis>a.dis;}

 }noww;

 //bool operator <(const strdis &a,const strdis &b){return a.dis<b.dis;}

 priority_queue <strdis> q;

 bool vis[maxn];

 long long dis[maxn];

 int main()

 {

     while(scanf("%d%d%d%d%d",&n,&m,&s,&p,&t)!=EOF)

     {

         memset(lin,,sizeof(lin));cnt=;

         memset(vis,,sizeof(vis));

         for(int i=;i<=m;i++)

         {

             int ai,bi,x;

             scanf("%d%d",&ai,&bi);

             for(int j=;j<=bi;j++)

             {

                 scanf("%d",&x);

                 insert(x,n+i,ai);

                 insert(n+i,x,);

             }

         }

         q.push((strdis){p,});

         memset(dis,0x3f,sizeof(dis));

         dis[p]=;

         while(!q.empty())

         {

             noww=q.top();

             q.pop();

             int nn=noww.x;

             if(vis[nn])continue;

             vis[nn]=;

             for(int i=lin[nn];i;i=e[i].next)

             {

                 int u=e[i].y;

                 if(dis[u]>dis[nn]+e[i].z)

                 {

                     dis[u]=dis[nn]+e[i].z;

                     q.push((strdis){u,dis[u]});

                 }

             }

         }

         if((!vis[s])||(!vis[t]))

         {

             printf("Poor guy, you don't have enough Money!\n");

         }

         else

         {

             printf("%lld\n",dis[s]+dis[t]);

         }

     }

     return ;

 }