比赛 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;
}