比赛 |
EYOI暨SBOI暑假快乐赛5th |
评测结果 |
TTTEEEEEEE |
题目名称 |
Sergey and Subway |
最终得分 |
0 |
用户昵称 |
HeSn |
运行时间 |
4.336 s |
代码语言 |
C++ |
内存使用 |
13.45 MiB |
提交时间 |
2022-06-29 10:45:51 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int n, m, d[1001], g[1001][1001] = {0}, g1[1010][1010], ok[1001];
long long ans = 0;
struct Node {
int n, dt;
bool operator < (const Node& x) const {
return x.dt < dt;
}
} nd;
priority_queue<Node> q;
int dfs(int st) {
memset(ok, 0, sizeof(ok));
memset(d, 0x3f, sizeof(d));
d[st] = 0;
nd.n = st;
nd.dt = d[st];
q.push(nd);
while(!q.empty()) {
int u = q.top().n;
q.pop();
if(ok[u]) {
continue;
}
ok[u] = 1;
for(int k = 1; k <= n; k ++)
if(g1[u][k] > -1 && !ok[k] && d[k] > d[u] + g1[u][k]) {
d[k] = d[u] + g1[u][k];
nd.n = k;
nd.dt = d[k];
q.push(nd);
}
}
for(int j = 1; j <= n; j ++) {
ans += d[j];
}
return 0;
}
int dfs1(int st) {
memset(ok, 0, sizeof(ok));
memset(d, 0x3f, sizeof(d));
d[st] = 0;
nd.n = st;
nd.dt = d[st];
q.push(nd);
while(!q.empty()) {
int u = q.top().n;
q.pop();
if(ok[u]) {
continue;
}
ok[u] = 1;
for(int k = 1; k <= n; k ++)
if(g[u][k] > -1 && !ok[k] && d[k] > d[u] + g[u][k]) {
d[k] = d[u] + g[u][k];
nd.n = k;
nd.dt = d[k];
q.push(nd);
}
}
for(int j = 1; j <= n; j ++) {
if(d[j] == 2) {
g1[st][j] = g1[j][st] = 1;
}
}
return 0;
}
int main()
{
freopen("Sergeyas.in","r",stdin);
freopen("Sergeyas.out","w",stdout);
int i, x, y, w;
cin >> n;
memset(g, -1, sizeof(g));
memset(g1, -1, sizeof(g1));
for(i = 1; i <= n - 1; i ++) {
cin >> x >> y;
g[x][y] = g[y][x] = g1[x][y] = g1[y][x] = 1;
}
for(i = 1; i <= n; i ++) {
dfs1(i);
}
for(i = 1; i <= n; i ++) {
dfs(i);
}
cout << ans / 2;
return 0;
}