用户输出
1
2
1
系统信息
Exited with return code 0| 编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
|---|---|---|---|---|---|---|---|---|
| #9560 | #1067. 1-08F. JM的俸俸伲购美病 | Accepted | 100 | 3407 ms | 3348 K | C++ 11 / 1.3 K | RBTsDefoliation | 2019-07-03 9:57:08 |
#include <bits/stdc++.h>
#define MAXN 505
#define INF 1000000000
using namespace std;
struct Graph {
int n, m;
int w[MAXN][MAXN];
int dist[MAXN][MAXN];
int cnt[MAXN][MAXN];
void build(int size) {
n = size;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) w[i][j] = INF;
}
void add(int u, int v, int weight) { w[u][v] = min(w[u][v], weight); }
void floyd() {
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) dist[i][j] = i == j ? 0 : w[i][j];
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
for (int k = 1; k <= n; ++k)
if (dist[i][k] + w[k][j] == dist[i][j])
++cnt[i][j];
}
int query(int x, int y) {
int ret = 0;
for (int i = 1; i <= n; ++i)
if (dist[x][i] + dist[i][y] == dist[x][y])
ret += cnt[x][i];
return ret;
}
};
Graph g;
int main() {
int n, m, q;
scanf("%d %d %d", &n, &m, &q);
g.build(n);
int u, v, w;
for (int i = 0; i < m; ++i) {
scanf("%d %d %d", &u, &v, &w);
g.add(u, v, w);
g.add(v, u, w);
}
g.floyd();
for (int i = 0; i < q; ++i) {
scanf("%d %d", &u, &v);
printf("%d\n", g.query(u, v));
}
return 0;
}用户输出
1
2
1
系统信息
Exited with return code 0500 124750 124750
1 2 17
1 3 39
1 4 650
1 5 388
1 6 655
1 7 606
1 8 845
1 9 723
1 10 171
1
<2623105 bytes omitted>14
5
9
7
4
15
8
2
5
8
2
15
9
5
8
6
10
9
6
3
2
15
7
7
6
6
7
5
12
9
6
4
<390638 bytes omitted>用户输出
14
5
9
7
4
15
8
2
5
8
2
15
9
5
8
6
10
9
6
3
2
15
7
7
6
6
7
5
12
9
6
4
5
9
9
2
3
5
6
5
6
5
2
6
3
14
7
2
5
15
8
5
5
7
6
12
4
4
4
2
<265860 bytes omitted>系统信息
Exited with return code 0500 124750 124750
1 2 17
1 3 39
1 4 650
1 5 388
1 6 655
1 7 606
1 8 845
1 9 723
1 10 171
1
<2623105 bytes omitted>14
5
9
7
4
15
8
2
5
8
2
15
9
5
8
6
10
9
6
3
2
15
7
7
6
6
7
5
12
9
6
4
<390638 bytes omitted>用户输出
14
5
9
7
4
15
8
2
5
8
2
15
9
5
8
6
10
9
6
3
2
15
7
7
6
6
7
5
12
9
6
4
5
9
9
2
3
5
6
5
6
5
2
6
3
14
7
2
5
15
8
5
5
7
6
12
4
4
4
2
<265860 bytes omitted>系统信息
Exited with return code 0500 124750 124750
1 2 17
1 3 39
1 4 650
1 5 388
1 6 655
1 7 606
1 8 845
1 9 723
1 10 171
1
<2623105 bytes omitted>14
5
9
7
4
15
8
2
5
8
2
15
9
5
8
6
10
9
6
3
2
15
7
7
6
6
7
5
12
9
6
4
<390638 bytes omitted>用户输出
14
5
9
7
4
15
8
2
5
8
2
15
9
5
8
6
10
9
6
3
2
15
7
7
6
6
7
5
12
9
6
4
5
9
9
2
3
5
6
5
6
5
2
6
3
14
7
2
5
15
8
5
5
7
6
12
4
4
4
2
<265860 bytes omitted>系统信息
Exited with return code 0500 124750 124750
1 2 17
1 3 39
1 4 650
1 5 388
1 6 655
1 7 606
1 8 845
1 9 723
1 10 171
1
<2623105 bytes omitted>14
5
9
7
4
15
8
2
5
8
2
15
9
5
8
6
10
9
6
3
2
15
7
7
6
6
7
5
12
9
6
4
<390638 bytes omitted>用户输出
14
5
9
7
4
15
8
2
5
8
2
15
9
5
8
6
10
9
6
3
2
15
7
7
6
6
7
5
12
9
6
4
5
9
9
2
3
5
6
5
6
5
2
6
3
14
7
2
5
15
8
5
5
7
6
12
4
4
4
2
<265860 bytes omitted>系统信息
Exited with return code 0500 124750 124750
1 2 17
1 3 39
1 4 650
1 5 388
1 6 655
1 7 606
1 8 845
1 9 723
1 10 171
1
<2623105 bytes omitted>14
5
9
7
4
15
8
2
5
8
2
15
9
5
8
6
10
9
6
3
2
15
7
7
6
6
7
5
12
9
6
4
<390638 bytes omitted>用户输出
14
5
9
7
4
15
8
2
5
8
2
15
9
5
8
6
10
9
6
3
2
15
7
7
6
6
7
5
12
9
6
4
5
9
9
2
3
5
6
5
6
5
2
6
3
14
7
2
5
15
8
5
5
7
6
12
4
4
4
2
<265860 bytes omitted>系统信息
Exited with return code 0500 124750 124750
1 2 17
1 3 39
1 4 650
1 5 388
1 6 655
1 7 606
1 8 845
1 9 723
1 10 171
1
<2623105 bytes omitted>14
5
9
7
4
15
8
2
5
8
2
15
9
5
8
6
10
9
6
3
2
15
7
7
6
6
7
5
12
9
6
4
<390638 bytes omitted>用户输出
14
5
9
7
4
15
8
2
5
8
2
15
9
5
8
6
10
9
6
3
2
15
7
7
6
6
7
5
12
9
6
4
5
9
9
2
3
5
6
5
6
5
2
6
3
14
7
2
5
15
8
5
5
7
6
12
4
4
4
2
<265860 bytes omitted>系统信息
Exited with return code 0500 124750 124750
1 2 17
1 3 39
1 4 650
1 5 388
1 6 655
1 7 606
1 8 845
1 9 723
1 10 171
1
<2623105 bytes omitted>14
5
9
7
4
15
8
2
5
8
2
15
9
5
8
6
10
9
6
3
2
15
7
7
6
6
7
5
12
9
6
4
<390638 bytes omitted>用户输出
14
5
9
7
4
15
8
2
5
8
2
15
9
5
8
6
10
9
6
3
2
15
7
7
6
6
7
5
12
9
6
4
5
9
9
2
3
5
6
5
6
5
2
6
3
14
7
2
5
15
8
5
5
7
6
12
4
4
4
2
<265860 bytes omitted>系统信息
Exited with return code 0500 124750 124750
1 2 17
1 3 39
1 4 650
1 5 388
1 6 655
1 7 606
1 8 845
1 9 723
1 10 171
1
<2623105 bytes omitted>14
5
9
7
4
15
8
2
5
8
2
15
9
5
8
6
10
9
6
3
2
15
7
7
6
6
7
5
12
9
6
4
<390638 bytes omitted>用户输出
14
5
9
7
4
15
8
2
5
8
2
15
9
5
8
6
10
9
6
3
2
15
7
7
6
6
7
5
12
9
6
4
5
9
9
2
3
5
6
5
6
5
2
6
3
14
7
2
5
15
8
5
5
7
6
12
4
4
4
2
<265860 bytes omitted>系统信息
Exited with return code 0500 124750 124750
1 2 17
1 3 39
1 4 650
1 5 388
1 6 655
1 7 606
1 8 845
1 9 723
1 10 171
1
<2623105 bytes omitted>14
5
9
7
4
15
8
2
5
8
2
15
9
5
8
6
10
9
6
3
2
15
7
7
6
6
7
5
12
9
6
4
<390638 bytes omitted>用户输出
14
5
9
7
4
15
8
2
5
8
2
15
9
5
8
6
10
9
6
3
2
15
7
7
6
6
7
5
12
9
6
4
5
9
9
2
3
5
6
5
6
5
2
6
3
14
7
2
5
15
8
5
5
7
6
12
4
4
4
2
<265860 bytes omitted>系统信息
Exited with return code 0