9/10
题A 18114 Ly and PostCards
题意：要发明信片，有n个人，选其中的k个人来发，但是有一个规定，就是选了a的话，如果a和b关系好的，b也要寄给，所以给出m对关系好的，让你随机选k个人，求最后要发给的人数的期望，为了不输出浮点数，就将结果乘以C（n，k）；
题解：期望题一般都是考虑各种情况，把所有情况都考虑清晰之后，将数加起来平均一下就可以得出答案。考虑一个人，如果选了他，那么C（n，k）中有多少种情况会导致选这个人呢？假设这个人的前面有cnt个人，也就是只要选了这cnt个人的其中一个的话，那么就会选到这个人，然后共有C（n，k）- C（n - cnt， k）种是会选到这cnt个人的，所以考虑每个点dfs一次算出cnt就可以了。
1 /*zhen hao*/
2 #include <cstdio>
3 #include <cstring>
4 #include <iostream>
5 #include <algorithm>
6 using namespace std;
7
8 typedef long long ll;
9 const int maxn = 55, maxm = 1e5 + 10;
10 int n, m, k, tot;
11 int head[maxn], cnt[maxn];
12 ll c[maxn][maxn];
13 bool vis[maxn];
14
15 struct Edge {
16 int v, next;
17 Edge(int v=0, int next=0) : v(v), next(next) {}
18 } edges[maxm];
19
20 void init() {
21 c[0][0] = 1;
22 for (int i = 1; i < maxn; i++) {
23 c[i][0] = c[i - 1][0];
24 for (int j = 1; j <= i; j++)
25 c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
26 }
27
28 memset(head, -1, sizeof head);
29 tot = 0;
30 }
31
32 void add_edge(int u, int v) {
33 edges[tot] = Edge(v, head[u]);
34 head[u] = tot++;
35 }
36
37 void dfs(int u) {
38 vis[u] = 1;
39 for (int i = head[u]; ~i; i = edges[i].next) {
40 int v = edges[i].v;
41 if (!vis[v]) dfs(v);
42 }
43 }
44
45 int main() {
46 // freopen("case.in", "r", stdin);
47 int T;
48 cin >> T;
49 while (T--) {
50 scanf("%d%d%d", &n, &m, &k);
51 init();
52 for (int i = 0; i < m; i++) {
53 int u, v;
54 scanf("%d%d", &u, &v);
55 add_edge(v, u);
56 }
57 for (int i = 1; i <= n; i++) {
58 memset(vis, false, sizeof vis);
59 dfs(i);
60 cnt[i] = 0;
61 for (int j = 1; j <= n; j++) cnt[i] += vis[j];
62 }
63 ll ans = 0;
64 for (int i = 1; i <= n; i++) {
65 ans += c[n][k] - c[n - cnt[i]][k];
66 }
67 cout << ans << endl;
68 }
69 return 0;
70 }
题B 18113 Secret Book of Kungfu
题意：定义一种数，该数的十进制表示是它的二进制表示的子串，求l，r中有多少个数满足？
题解：打表发现这种数只可能是0和1组成，那么对于这个区间的所有0和1组成的十进制数，暴力统计一下有多少个，打个表二分查找即可。
1 /*zhen hao*/
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 #include <iostream>
6 #include <cmath>
7 #include <vector>
8 #include <queue>
9 #include <stack>
10 #include <string>
11 using namespace std;
12
13 typedef long long ll;
14 const ll inf = 1e15;
15 char s[100], t[100];
16 int dp[1 << 20], digit[100], cnt;
17 ll id[1 << 20];
18
19 int check(int l, int r) {
20 int ret = 0;
21 for (int i = l; i <= r; i++) {
22 int ss = 0, st = 0;
23 int x = i;
24 while (x) {
25 s[ss++] = (x % 2) + '0';
26 x /= 2;
27 }
28 s[ss] = ' ';
29 reverse(s,s + ss);
30 x = i;
31 while (x) {
32 t[st++] = (x % 10) + '0';
33 x /= 10;
34 }
35 t[st] = ' ';
36 reverse(t, t + st);
37 if (strstr(s, t) != NULL) {
38 ret++;
39 }
40 }
41 return ret;
42 }
43
44 int check(ll v) {
45 ll x = v;
46 int ss = 0, st = 0;
47 while (x) {
48 s[ss++] = (x % 2) + '0';
49 x /= 2;
50 }
51 s[ss] = ' ';
52 x = v;
53 while (x) {
54 t[st++] = (x % 10) + '0';
55 x /= 10;
56 }
57 t[st] = ' ';
58 return strstr(s, t) != NULL;
59 }
60
61 void init() {
62 for (int i = 0; i < (1 << 16); i++) {
63 ll val = 0;
64 int x = i, len = 0;
65 while (x) {
66 digit[len++] = x % 2;
67 x /= 2;
68 }
69 for (int j = len - 1; j >= 0; j--) val = val * 10 + digit[j];
70 if (check(val)) dp[i] = dp[i - 1] + 1;
71 else dp[i] = dp[i - 1];
72 id[i] = val;
73 cnt++;
74 if (val > inf) break;
75 }
76 }
77
78 int get_ans(ll n) {
79 if (n == -1) return 0;
80 if (n == 0) return 1;
81 int len = 0;
82 ll real = 0;
83 while (n) {
84 digit[++len] = n % 10;
85 n /= 10;
86 }
87 bool flag = false;
88 for (int i = len; i > 0; i--) {
89 if (digit[i] > 1) flag = true;
90 if (flag) real = real * 10 + 1;
91 else real = real * 10 + digit[i];
92 }
93 int pos = lower_bound(id, id + cnt, real) - id;
94 return dp[pos];
95 }
96
97 int main() {
98 // freopen("case.in", "r", stdin);
99 init();
100 int T;
101 cin >> T;
102 while (T--) {
103 ll l, r;
104 cin >> l >> r;
105 printf("%d
", get_ans(r) - get_ans(l - 1));
106 // printf("%d
", check(l, r));
107 }
108 return 0;
109 }
题C 18116 M1crosoft Exce1
题意：模拟题
题解：搞不定啊！希望有生之年能够把bug搞定吧！！
题D 18117 Yys VS BetaCome
题意：给你一段连续的区间长度为n，每次可以取长度为1~m的连续区间，谁取到最后的线段算赢，问你最后谁赢。
题解：这题是全场最水的题目，当然是对于学过对称博弈的大神，对于我这种渣渣当然是一个dfs打个表就交上去了。说一下正解：当m = 1的时候判一下奇偶就好了，否则的话就一定是先手必胜，因为第一个人拿了中间长度之后，然后分成均匀的两端，左边的人怎么拿，同理拿右边的就好了，这样就一定能够获胜。下面就给出我这个渣渣打表的代码吧！
1 /*zhen hao*/
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 #include <iostream>
6 #include <cmath>
7 #include <vector>
8 #include <queue>
9 #include <stack>
10 using namespace std;
11
12 const int maxn = 210, maxk = 110;
13 int dp[maxn][maxk];
14
15 int dfs(int n, int k) {
16 if (dp[n][k] != -1) return dp[n][k];
17 if (k >= n) return 1;
18 bool ok = false;
19 for (int i = 1; i <= k; i++)
20 if (!dfs(n - i, k)) {
21 ok = true; break;
22 }
23 if (!ok) {
24 for (int i = 1; i <= k; i++) {
25 for (int l = 1; l < n - i; l++) {
26 int r = n - i - l;
27 if (!(dfs(l, k) ^ dfs(r, k))) ok = true;
28 if (ok) break;
29 }
30 }
31 }
32 return dp[n][k] = ok;
33 }
34
35 void init() {
36 memset(dp, -1, sizeof dp);
37 for (int i = 1; i <= 200; i++)
38 for (int j = 1; j <= 40; j++)
39 dp[i][j] = dfs(i, j);
40 }
41
42 int main() {
43 // freopen("case.in", "r", stdin);
44 init();
45 int T;
46 cin >> T;
47 while (T--) {
48 int n, k;
49 cin >> n >> k;
50 if (dp[n][k]) puts("yes");
51 else puts("no");
52 }
53 return 0;
54 }
题E 18110 Koishi's travel, Satori's travel
题意：给你n个数，找出最大的ai % aj （i > j）
题解：这个数的范围是5e4，显然是从这里下手。然后对于一个数aj，模aj的数的结果如下：0 1 …… （ai - 1） 0 1 …… （ai - 1）这样循环地出现，所以每次我们检查一段段的看一下这一段的最大值是什么，这个显然可以用线段树进行维护，对于每个数要找n / ai次，每次logn，所以复杂度是O（nlog2n）；还有一个优化，对于每个相同的数，要考虑的肯定是最后一个，因为这样考虑的数更多。
1 /*zhen hao*/
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 #include <iostream>
6 #include <cmath>
7 #include <vector>
8 #include <queue>
9 #include <stack>
10 #include <string>
11 using namespace std;
12
13 #define lson l, m, rt<<1
14 #define rson m+1, r, rt<<1|1
15
16 const int maxn = 5e4 + 10;
17 int last[maxn], _max[maxn * 4], v[maxn];
18
19 void PU(int rt) {
20 _max[rt] = max(_max[rt * 2], _max[rt * 2 + 1]);
21 }
22
23 void build(int l, int r, int rt) {
24 _max[rt] = 0;
25 if (l == r) return;
26 int m = (l + r) / 2;
27 build(lson);
28 build(rson);
29 }
30
31 void update(int u, int d, int l, int r, int rt) {
32 if (l == r) {
33 _max[rt] = d;
34 return;
35 }
36 int m = (l + r) / 2;
37 if (u <= m) update(u, d, lson);
38 else update(u, d, rson);
39 PU(rt);
40 }
41
42 int query(int ql, int qr, int l, int r, int rt) {
43 if (ql <= l && r <= qr) {
44 return _max[rt];
45 }
46 int m = (l + r) / 2, ret = 0;
47 if (ql <= m) ret = max(ret, query(ql, qr, lson));
48 if (qr > m) ret = max(ret, query(ql, qr, rson));
49 return ret;
50 }
51
52 int main() {
53 // freopen("case.in", "r", stdin);
54 int T;
55 cin >> T;
56 while (T--) {
57 int n;
58 scanf("%d", &n);
59 for (int i = 1; i <= n; i++) {
60 scanf("%d", v + i);
61 last[v[i]] = i;
62 }
63 build(0, n, 1);
64 int ans = 0;
65 for (int i = 1; i <= n; i++) {
66 if (i == last[v[i]]) {
67 int l = 0, r;
68 while (l <= n) {
69 r = min(n, l + v[i] - 1);
70 int tmp = query(l, r, 0, n, 1);
71 // printf("%d %d %d
", l, r, tmp);
72 ans = max(ans, tmp % v[i]);
73 l += v[i];
74 }
75 }
76 update(v[i], v[i], 0, n, 1);
77 }
78 cout << ans << endl;
79 }
80 return 0;
81 }
题F 18115 Devon's 3D LED Cube
题意：给你n * m * k的开关和灯，然后开关有一个特性，就是按下这个开关之后对应的六个方向的开关（三维）都会取反，然后问你最少按下多少个开关可以得到灯全开的状态。
题解：这道题和BC的一道div1第三题很像，只不过换成三维的了。做法就是：枚举第一层（m * k）的开关状态，然后结合第一层的灯的起始和终止（已知）状态，可以推出第二层的开关状态，最后推导出最后一层的开关状态，然后在判断能不能将最后一层的开关给点亮。
1 #include <cstdio>
2 #include <cstring>
3 #include <cmath>
4 #include <iostream>
5 #include <algorithm>
6 #include <vector>
7 #include <queue>
8 #include <set>
9 #include <map>
10 #include <stack>
11 using namespace std;
12
13 const int maxn = 5, dx[] = {-1, 0, 0, 0, 0, 0}, dy[] = {0, 1, -1, 0, 0, 0}, dz[] = {0, 0, 0, 1, -1, 0}, inf = 1 << 20;
14 int n, m,k;
15 int v[maxn][maxn][maxn], s[maxn][maxn][maxn];
16
17 bool inside(int x, int y, int z) {
18 return x >= 0 && x < n && y >= 0 && y < m && z >= 0 && z < k;
19 }
20
21 int get_around(int x, int y, int z) {
22 int ret = 0;
23 for (int i = 0; i < 6; i++) {
24 int xx = x + dx[i], yy = y + dy[i], zz = z + dz[i];
25 if (!inside(xx, yy, zz)) continue;
26 ret += s[xx][yy][zz];
27 }
28 return ret;
29 }
30
31 bool check() {
32 for (int i = 0; i < n - 1; i++)
33 for (int j = 0; j < m; j++)
34 for (int l = 0; l < k; l++) {
35 s[i + 1][j][l] = (get_around(i, j, l) + v[i][j][l] + 1) % 2;
36 }
37 for (int j = 0; j < m; j++)
38 for (int l = 0; l < k; l++) {
39 int x = get_around(n - 1, j, l);
40 if ((x + v[n - 1][j][l]) % 2 != 1) return false;
41 }
42 return true;
43 }
44
45 int main() {
46 // freopen("case.in", "r", stdin);
47 int T;
48 cin >> T;
49 while (T--) {
50 scanf("%d%d%d", &n, &m, &k);
51 for (int i = 0; i < n; i++)
52 for (int j = 0; j < m; j++)
53 for (int l = 0; l < k; l++)
54 scanf("%d", &v[i][j][l]);
55 int ans = inf, cnt = m * k;
56 for (int i = 0; i < (1 << cnt); i++) {
57 for (int j = 0; j < cnt; j++) {
58 int x = j / k, y = j % k;
59 if (i & (1 << j)) s[0][x][y] = 1;
60 else s[0][x][y] = 0;
61 }
62 if (check()) {
63 int temp = 0;
64 for (int i = 0; i < n; i++)
65 for (int j = 0; j < m; j++)
66 for (int l = 0; l < k; l++)
67 temp += s[i][j][l];
68 ans = min(ans, temp);
69 }
70 }
71 if (ans == inf) ans = -1;
72 cout << ans << endl;
73 }
74 return 0;
75 }
题G 18108 chocola isn't so skillful
题意：给你一种形状有五个格子，然后有a b c d e满足a + b + c = d + e + c，这个c是共用的，且这五个数都不能相同，问你有多少种填法。
题解：这题数据范围很小，我们可以枚举a b c然后d已经确定了，然后c有多少种取法呢，就是n - 4,累计一下即可。
1 /*zhen hao*/
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 #include <iostream>
6 #include <cmath>
7 #include <vector>
8 #include <queue>
9 #include <stack>
10 using namespace std;
11
12 int main() {
13 // freopen("case.in", "r", stdin);
14 int T;
15 cin >> T;
16 while (T--) {
17 int n, ans = 0;
18 scanf("%d", &n);
19 for (int i = 1; i <= n; i++)
20 for (int j = 1; j <= n; j++) if (i != j) {
21 int s = i + j;
22 for (int k = 1; k <= s; k++) if (k >= 1 && k <= n && k != i && k != j && k != s - k && s - k >= 1 && s - k <= n && s - k != i && s - k != j) {
23 ans += (n - 4);
24 }
25 }
26 cout << ans << endl;
27 }
28 return 0;
29 }
题H 18109 Koishi and Kokoro, no one loses
题意：给你n和m，然后求有多少个满足下列条件的长度为m的序列
（1）序列是非递减的
（2）序列的数的范围是【1，n】
（3）满足A[1] * A[2] * ...... * A[m] = lcm(A[1], A[2], ....,A[m]) * gcd(A[1], A[2],...A[m])
题解：实际上要想lcm * gcd必须是这m个数是互素的，所以题目就是求长度为m的互素的非递减序列有多少种？分析一下数据规模，n为100，里面的素因子种类有25个，我们观察可以发现，一个数存在两种素因子的最小的是50（5和2），在后面的数如果有两个素因子的话一定是50以内的，所以我们就可以用dp(i, j, k)表示长度为i的序列，考虑j这个数作为末尾，素因子的状态为k，由于50以内有15个素因子，所以k的取值为（1 << 15）;然后就是转移了，显然枚举j + 1 …… 100作为末尾，但前提是对k状态没有冲突，这个要写一个函数来判断，然后加进这个数之后状态有什么变化，也要写个函数。对于这两个函数的所有结果用两个数组分别保存，最后记得统计一下答案即可。
1 /*zhen hao*/
2 #include <cstdio>
3 #include <iostream>
4 #include <cstring>
5 #include <algorithm>
6 #include <cmath>
7 #include <vector>
8 using namespace std;
9
10 typedef long long ll;
11 const int mod = 1e9 + 7;
12 int dp[30][110][1 << 15], id[110], prime[110], f[110], to[110][1 << 15];
13 int ans[40][140];
14 bool vis[110][1 << 15];
15
16
17 bool check(int x, int s) {
18 for (int i = 0; i < 15; i++) if (x % prime[i] == 0) {
19 if (s & (1 << i)) return false;
20 }
21 return true;
22 }
23
24 int get_status(int x, int s) {
25 for (int i = 0; i < 15; i++) if (x % prime[i] == 0) {
26 s |= (1 << i);
27 }
28 return s;
29 }
30
31 void init() {
32 id[0] = id[1] = 1;
33 for (int i = 2; i <= 50; i++) if (!id[i])
34 for (int j = i + i; j <= 50; j += i) id[j] = 1;
35 int cnt = 0;
36 for (int i = 2; i <= 50; i++)
37 if (!id[i]) prime[cnt++] = i;
38 // for (int i = 0; i < cnt; i++) cout << prime[i] << ' ';
39 // cout << cnt << endl;
40 for (int x = 2; x <= 100; x++)
41 for (int y = 0; y < (1 << 15); y++) if (check(x, y)) {
42 vis[x][y] = 1;
43 to[x][y] = get_status(x, y);
44 }
45 }
46
47 void add(int& a, int b) {
48 a += b;
49 if (a >= mod) a -= mod;
50 }
51
52 void slove() {
53 dp[0][0][0] = 1;
54 for (int i = 0; i < 25; i++) {
55 for (int j = i; j <= 100; j++) {
56 for (int k = 0; k < (1 << 15); k++) if (dp[i][j][k]) {
57 // cout << i << ' ' << j << ' ' << k << endl;
58 for (int x = max(2, j + 1); x <= 100; x++) if (vis[x][k])
59 add(dp[i + 1][x][to[x][k]], dp[i][j][k]);
60 }
61 }
62 }
63 for (int i = 1; i <= 25; i++) {
64 for (int j = i; j <= 100; j++) {
65 for (int k = 0; k < (1 << 15); k++) {
66 add(ans[i][j], dp[i][j][k]);
67 }
68 }
69 }
70 }
71
72 int get_ans(int n, int m) {
73 int ret = 1;
74 for (int i = 1; i <= min(25, m); i++)
75 for (int j = i; j <= min(100, n); j++)
76 add(ret, ans[i][j]);
77 return ret;
78 }
79
80 int main() {
81 // freopen("case.in", "r", stdin);
82 init();
83 slove();
84 int T;
85 scanf("%d", &T);
86 while (T--) {
87 int n, m;
88 scanf("%d%d", &n, &m);
89 if (m == 2) printf("%d
", n * (n + 1) / 2);
90 else {
91 printf("%d
", get_ans(n, m));
92 }
93 }
94 return 0;
95 }
题I 18111 Maximum Perimeter
题意：给你一个四边形，让你切成两个三角形，然后组成的三角形周长最大。
题解：首先要看这个四边形是不是凸的。如果是凸的，直接枚举两种情况，如果不是，那么就找出那个导致四边形是凹的的点，然后直接和另外一个点分成两个三角形即可。
1 /*zhen hao*/
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 #include <iostream>
6 #include <cmath>
7 #include <vector>
8 #include <queue>
9 #include <stack>
10 #include <string>
11 using namespace std;
12
13 const double eps = 1e-8;
14
15 int sgn(double x) {
16 if (fabs(x) < eps) return 0;
17 if (x < 0) return -1;
18 return 1;
19 }
20
21 struct Point {
22 double x, y;
23 Point() {}
24 Point(double _x, double _y) {
25 x = _x; y = _y;
26 }
27 void input() {
28 scanf("%lf%lf", &x, &y);
29 }
30 double operator ^ (const Point& b) const {
31 return x * b.y - y * b.x;
32 }
33 Point operator - (const Point& b) const {
34 return Point(x - b.x, y - b.y);
35 }
36 double dist(Point b) {
37 return sqrt((x - b.x) * (x - b.x) + (y - b.y) * (y - b.y));
38 }
39 double operator * (const Point& b) const {
40 return x * b.x + y * b.y;
41 }
42 };
43
44 struct Polygon {
45 int n;
46 Point p[5];
47 int relationpoint(Point q) {
48 int cnt = 0;
49 for (int i = 0; i < n; i++) {
50 int j = (i + 1) % n;
51 int k = sgn((q - p[j]) ^ (p[i] - p[j]));
52 int u = sgn(p[i].y - q.y);
53 int v = sgn(p[j].y - q.y);
54 if (k > 0 && u < 0 && v >= 0) cnt++;
55 if (k < 0 && v < 0 && u >= 0) cnt--;
56 }
57 return cnt != 0;
58 }
59 };
60
61 Polygon poly[10];
62 Point p[5];
63
64 int main() {
65 // freopen("case.in", "r", stdin);
66 int T;
67 cin >> T;
68 while (T--) {
69 int n = 4;
70 for (int i = 0; i < n; i++) p[i].input();
71 for (int i = 0; i < n; i++) {
72 int cnt = 0;
73 for (int j = 0; j < n; j++) if (i != j) poly[i].p[cnt++] = p[j];
74 poly[i].n = cnt;
75 }
76 int t = -1;
77 for (int i = 0; i < n; i++) {
78 if (poly[i].relationpoint(p[i])) { t = i; break; }
79 }
80 double ans = 0;
81 for (int i = 0; i < 4; i++) ans += p[i].dist(p[(i + 1) % n]);
82 if (t == -1) {
83 ans += max(p[0].dist(p[2]) * 2, p[1].dist(p[3]) * 2);
84 } else {
85 ans += p[t].dist(p[(t + 2) % 4]) * 2;
86 }
87 printf("%.3lf
", ans);
88 }
89 return 0;
90 }
题J 18112 Play Ball
题意：一开始给你一个人，坐标和速度，然后给你目标点，然后在给你n个可以辅助的人，做斜抛运动，然后问你最短时间到目标点。
题解：设这个时间为t，然后有
L = Vx t
Vy = g（t/2）
然后联立成一个一元二次方程再判有没有解即可，无解就说明这两个点是inf，注意每个人都有一个速度，所以是有向边。在最后跑一次最短路就行了。
1 /*zhen hao*/
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 #include <iostream>
6 #include <cmath>
7 #include <vector>
8 #include <queue>
9 #include <stack>
10 #include <string>
11 using namespace std;
12
13 typedef long long ll;
14 const int maxn = 20, maxm = 1e3 + 10;
15 const double inf = 1e10;
16 double dist[maxn];
17 int n, tot, head[maxn], done[maxn];
18
19 struct Point {
20 double x, y, v;
21 void input() {
22 scanf("%lf%lf%lf", &x, &y, &v);
23 }
24 double dist(Point o) {
25 double a = 25.0, b = v * v, c = (x - o.x) * (x - o.x) + (y - o.y) * (y - o.y);
26 double delta = b * b - 4 * a * c;
27 if (delta < 0) return inf;
28 double x1 = (b - sqrt(delta)) / (2.0 * a), x2 = (b + sqrt(delta)) / (2.0 * a);
29 if (x1 > 0 && x2 > 0) return sqrt(min(x1, x2));
30 if (x1 < 0 && x2 < 0) return inf;
31 return sqrt(max(x1, x2));
32 }
33 } p[maxn];
34
35 struct Edge {
36 int v;
37 double w;
38 int next;
39 Edge(int v=0, double w=0, int next=0) : v(v), w(w), next(next) {}
40 } edges[maxm];
41
42 struct Node {
43 double d;
44 int u;
45 Node(double d=0, int u=0) : d(d), u(u) {}
46 bool operator < (const Node& o) const {
47 return d > o.d;
48 }
49 };
50
51 void init() {
52 tot = 0;
53 memset(head, -1, sizeof head);
54 }
55
56 void add_edge(int u, int v, double w) {
57 edges[tot] = Edge(v, w, head[u]);
58 head[u] = tot++;
59 }
60
61 void dijkstra() {
62 for (int i = 0; i <= n; i++) dist[i] = inf;
63 memset(done, 0, sizeof done);
64 dist[0] = 0;
65 priority_queue<Node> pq;
66 pq.push(Node(0, 0));
67 while (!pq.empty()) {
68 Node r = pq.top(); pq.pop();
69 int u = r.u;
70 if (done[u]) continue;
71 done[u] = 1;
72 for (int i = head[u]; ~i; i = edges[i].next) {
73 Edge& e = edges[i];
74 if (dist[e.v] > dist[u] + e.w) {
75 dist[e.v] = dist[u] + e.w;
76 pq.push(Node(dist[e.v], e.v));
77 }
78 }
79 }
80 }
81
82
83 int main() {
84 // freopen("case.in", "r", stdin);
85 int T;
86 cin >> T;
87 while (T--) {
88 p[0].input();
89 scanf("%d", &n);
90 for (int i = 1; i <= n; i++) p[i].input();
91 ++n;
92 scanf("%lf%lf", &p[n].x, &p[n].y);
93
94 init();
95 for (int i = 0; i < n; i++)
96 for (int j = 0; j <= n; j++) if (i != j) {
97 double w = p[i].dist(p[j]);
98 if (w != inf) add_edge(i, j, w);
99 }
100 dijkstra();
101 printf("%.3lf
", dist[n]);
102 }
103 return 0;
104 }
最后一个福利：题目 + 州神题解