JZOJ 5771. 【NOIP2008模擬】遨游

5771. 【NOIP2008模擬】遨游 
(File IO): input:trip.in output:trip.out

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。

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

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <cmath>
  5 #include <queue>
  6 #define M 500007
  7 #define N 200007
  8 using namespace std;
  9 struct edge
 10 {
 11     int to, next;
 12     double val;
 13 }e[N];
 14 int n, m, ls[N], x[N], y[N], t[N], start, end, tot, tma, tin = 10000007, l, r, dis[N], L, R, ans1, ans2;
 15 double z[N], cut[N];
 16 bool v[N], b[N];
 17 queue<int> q;
 18 
 19 void add(int u, int v, double w)
 20 {
 21     e[++tot].to = v;
 22     e[tot].next = ls[u];
 23     e[tot].val = w;
 24     ls[u] = tot;
 25     e[++tot].to = u;
 26     e[tot].next = ls[v];
 27     e[tot].val = w;
 28     ls[v] = tot;
 29 }
 30 
 31 void init()
 32 { 
 33     scanf("%d%d", &n, &m);
 34     for (int i = 1; i <= m; i++)
 35         scanf("%d%d%lf", &x[i], &y[i], &z[i]);
 36     for (int i = 1; i <= n; i++)
 37     {
 38         int T, u;
 39         scanf("%d", &T);
 40         for (int j = 1; j <= T; j++)
 41             scanf("%d", &u), t[u] = i;
 42     }
 43     for (int i = 1; i <= n; i++)
 44         scanf("%lf", &cut[i]), cut[i] /= 100;
 45     scanf("%d%d", &start, &end);
 46     for (int i = 1; i <= m; i++)
 47     {
 48         if (t[x[i]] != t[y[i]])
 49         {
 50             add(x[i], y[i], z[i] * ((cut[t[x[i]]] + cut[t[y[i]]]) / 2));
 51             tin = min(tin, (int)(z[i] * ((cut[t[x[i]]] + cut[t[y[i]]]) / 2)));
 52             tma = max(tma, (int)(z[i] * ((cut[t[x[i]]] + cut[t[y[i]]]) / 2)));
 53         }
 54         else
 55         {
 56             add(x[i], y[i], z[i] * cut[t[x[i]]]);
 57             tin = min(tin, (int)(z[i] * ((cut[t[x[i]]] + cut[t[y[i]]]) / 2)));
 58             tma = max(tma, (int)(z[i] * ((cut[t[x[i]]] + cut[t[y[i]]]) / 2)));
 59         }
 60     }
 61 }
 62 
 63 bool check(int judge1, int judge2)
 64 {
 65     memset(v, 0, sizeof(v));
 66     for (int i = 1; i <= tot; i++)
 67         if (e[i].val >= judge1 && e[i].val <= judge2) v[i] = 1;
 68     memset(b, 0, sizeof(b));
 69     memset(dis, 0x7f7f7f7f, sizeof(dis));
 70     dis[start] = 0;
 71     q.push(start);
 72     b[start] = 1;
 73     while (!q.empty())
 74     {
 75         int now = q.front();
 76         q.pop();
 77         for (int i = ls[now]; i; i = e[i].next)
 78         {
 79             if (!v[i])    continue;
 80             if (dis[now] + 1 >= dis[e[i].to])    continue;
 81             dis[e[i].to] = dis[now] + 1;
 82             if (b[e[i].to])    continue;
 83             q.push(e[i].to);
 84             b[e[i].to] = 1;
 85         }
 86         b[now] = 0;
 87     }
 88     if (dis[end] != 0x7f7f7f7f)    return 1;
 89     return 0;
 90 }
 91 
 92 void work()
 93 {
 94     l = tin, r = tma + 1;
 95     while (l < r)
 96     {
 97         int mid = (l + r + 1) / 2;
 98         if (check(mid, tma + 1))    l = mid;
 99         else r = mid - 1;
100     }
101     L = l;
102     l = tin, r = tma + 1;
103     while (l < r)
104     {
105         int mid = (l + r) / 2;
106         if (check(L, mid))    r = mid;
107         else l = mid + 1;
108     }
109     R = l;
110     printf("%d %d", L, R);
111 }
112 
113 int main()
114 {
115     freopen("trip.in", "r", stdin);
116     freopen("trip.out", "w", stdout);
117     init();
118     work();
119 }