Description

     MWH寒假外出旅游，来到了S国。S国划分为N个省，第i个省有Ti座城市，编号分别为Ci1，Ci2，……CiTi（各省城市编号不会重复）。所有城市间有M条双向的道路连接，从任意一个城市出发，可到达一切城市，每条道路均须收费。

     此时恰逢春运期间，S国交通运输局采取了优惠措施。当一条路的路费在[L..R]区间时，可免去。同时，每个省也有优惠措施，第i个省内的每条道路路费收其Xi%，连接第i个省和第j个省的每条道路路费收其(Xi%+Xj%)/2。

MWH想从城市s走到城市t，请求出一对L，R，确保：

1. MWH能免费到达目的地；
2. L≤R；
3. L、R均为整数；
4. L尽可能地大，R在满足L最大的前提下最小。

注意：因每条道路由各省的交通运输局直接管辖，所以每条道路的路费必须先得到省级优惠，再得到国家级优惠。

Input

　　第一行两个整数N，M。

　　接下来M行，每行三个整数，u、v、w，表示连接u、v的道路需收费w。

　　接下来N行，第i+M+1行有一个整数Ti，后面Ti个整数，分别是Ci1..CiTi（所有城市编号保证按正整数顺序给出1..

 Ti）。

　　下一行N个整数X1..Xi。

　　最后一行，两个整数，s、t。

Output

　　一行两个整数，如题，L和R。

Sample Input

　　3 7　　1 2 3　　5 2 8　　1 3 7　　5 4 5　　2 4 9　　3 5 10　　3 4 2　　2 1 2　　1 3　　2 4 5　　30 50 60　　1 5 

Sample Output

2 6

Data Constraint

 Solution

　　二分，分别二分最大的l，并用二分出的最大的l再二分出最小的r。

1 #include 
       
          2 using namespace std;  3 struct arr   4 {   5     int x,y,next;  6     double w;  7 };  8 arr edge[1000000];  9 int ls[100000],n,m,fa[60000],s,ss,w,u; 10 double p[60000],ma; 11 bool pd(int x) 12 { 13     int l=0,r=1,d[1000000]; 14     d[1]=s; 15     bool f[100000]; 16     for (int i=1;i<=w;i++) 17         f[i]=true; 18     f[s]=false; 19     while (l
        
         =x&&f[edge[i].y]) 25             { 26                 d[++r]=edge[i].y; 27                 f[d[r]]=false; 28                 if (d[r]==ss) 29                     return true; 30             } 31             i=edge[i].next; 32         } 33     } 34     return false; 35 } 36 bool pdd(int x) 37 { 38     int l=0,r=1,d[1000000]; 39     d[1]=s; 40     bool f[100000]; 41     for (int i=1;i<=w;i++) 42         f[i]=true; 43     f[s]=false; 44     while (l
         
          =u) 50             { 51                 d[++r]=edge[i].y; 52                 f[d[r]]=false; 53                 if (d[r]==ss) 54                     return true; 55             } 56             i=edge[i].next; 57         } 58     } 59     return false; 60 } 61 int main() 62 { 63         scanf("%d%d",&n,&m); 64     for (int i=1;i<=m;i++) 65     { 66         scanf("%d%d%lf",&edge[i*2-1].x,&edge[i*2-1].y,&edge[i*2-1].w); 67         edge[i*2-1].next=ls[edge[i*2-1].x]; 68         ls[edge[i*2-1].x]=i*2-1; 69         edge[i*2].x=edge[i*2-1].y; 70         edge[i*2].y=edge[i*2-1].x; 71         edge[i*2].w=edge[i*2-1].w; 72         edge[i*2].next=ls[edge[i*2].x]; 73         ls[edge[i*2].x]=i*2; 74     } 75     for (int i=1;i<=n;i++) 76     { 77         int x,y; 78         scanf("%d",&x); 79         for (int j=1;j<=x;j++) 80         { 81             scanf("%d",&y); 82             fa[y]=i; 83             w++; 84         } 85     } 86     for (int i=1;i<=n;i++) 87         scanf("%lf",&p[i]); 88     scanf("%d%d",&s,&ss); 89     for (int i=1;i<=m*2;i++) 90     { 91         edge[i].w=edge[i].w*(p[fa[edge[i].x]]+p[fa[edge[i].y]])/200; 92         if (edge[i].w>ma) 93             ma=edge[i].w; 94     } 95     int l=0,r=(int)ma+1; 96     while (l
          
           0) l--;104     u=l;105     l=0;r=(int)ma+1;106     while (l