1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
| int n, m;
struct Edge {
int u, v, w;
} eg[MAXm + 10];
int dis[MAXn + 10][MAXn + 10];
void Floyd() {
for (int k = 1; k <= n; ++k) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
}
pair<int, int> tmp[MAXn + 10];
int rk[MAXn + 10][MAXn + 10];
void EvaRk() {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
tmp[j] = make_pair(dis[i][j], j);
}
sort(tmp + 1, tmp + 1 + n);
for (int j = 1; j <= n; ++j) {
rk[i][j] = tmp[j].second;
}
}
}
int dia;
int cenu, cenv, cendisu, cendisv;
void EvaDiaCen() {
dia = INF;
for (int i = 1; i <= m; ++i) {
int u = eg[i].u, v = eg[i].v, w = eg[i].w;
int mxdisv = dis[v][rk[u][n]];
for (int j = n - 1; j; --j) {
if (mxdisv <= dis[v][rk[u][j]]) {
if (dia > dis[u][rk[u][j]] + mxdisv + w) {
dia = dis[u][rk[u][j]] + mxdisv + w;
cenu = u;
cenv = v;
cendisu = dia / 2 - dis[u][rk[u][j]];
cendisv = dia / 2 - mxdisv;
}
mxdisv = dis[v][rk[u][j]];
}
}
}
}
bool vis[MAXn + 10];
int dist[MAXn + 10], from[MAXn + 10];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
void Dijkstra(int s) {
memset(dist, 0x3f, sizeof(dist));
dist[s] = 0;
pq.push(make_pair(0, s));
while (!pq.empty()) {
int cur = pq.top().second; pq.pop();
if (vis[cur]) continue;
vis[cur] = 1;
for (int i = head[cur]; i; i = nex[i]) {
if (vis[to[i]]) continue;
if (dist[to[i]] > dist[cur] + wei[i]) {
dist[to[i]] = dist[cur] + wei[i];
from[to[i]] = cur;
pq.push(make_pair(dist[to[i]], to[i]));
}
}
}
}
int cntmdst; pair<int, int> mdst[MAXm + 10];
void EvaMdst() {
for (int i = 1; i <= m; ++i) {
if (eg[i].u == cenu && eg[i].v == cenv) continue;
Insert(eg[i].u, eg[i].v, eg[i].w);
Insert(eg[i].v, eg[i].u, eg[i].w);
}
Insert(n + 1, cenu, cendisu);
Insert(cenu, n + 1, cendisu);
Insert(n + 1, cenv, cendisv);
Insert(cenv, n + 1, cendisv);
Dijkstra(n + 1);
for (int i = 1; i <= n; ++i) {
if (i == cenu || i == cenv) continue;
mdst[++cntmdst] = make_pair(i, from[i]);
}
mdst[++cntmdst] = make_pair(cenu, cenv);
}
signed main() {
Floyd();
EvaRk();
EvaDiaCen();
EvaMdst();
}
|
