用户输出
26
系统信息
Exited with return code 0
编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
---|---|---|---|---|---|---|---|---|
#88018 | #1388. 莉可莉丝 | Wrong Answer | 15 | 13810 ms | 2600 K | C++ 17 / 4.5 K | xhytom | 2023-05-07 21:02:57 |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, a, n) for (int i = n - 1; i >= a; i--)
#define fastio \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
#define multi \
int _; \
cin >> _; \
while (_--)
#define debug(x) cerr << #x << " = " << (x) << endl;
#define int long long
#define pb push_back
#define eb emplace_back
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }
void test() { cerr << "\n"; }
template <typename T, typename... Args>
void test(T x, Args... args) {
cerr << x << " ";
test(args...);
}
const ll MOD = 998244353;
// const ll MOD = 1e9+7;
const ll P1 = 999971, base1 = 101;
const ll P2 = 999973, base2 = 103;
const ll N = 20005;
// head
vector<pair<int, int> > e[20005];
int dis[N][3], fa[N][3], dep[N][3], fa1[N][25], fa2[N][25];
bool vis[N][3];
void dijsktra(int s, int idx) {
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
dis[s][idx] = 0;
q.push({ dis[s][idx], s });
while (!q.empty()) {
auto [_, x] = q.top();
q.pop();
if (vis[x][idx])
continue;
vis[x][idx] = 1;
for (auto [y, w] : e[x]) {
if (vis[y][idx])
continue;
if (dis[x][idx] + w < dis[y][idx]) {
dep[y][idx] = dep[x][idx] + 1;
fa[y][idx] = x;
dis[y][idx] = dis[x][idx] + w;
q.push({ dis[y][idx], y });
}
}
}
}
int lca1(int x, int y) {
// 令 y 比 x 深。
// cout << x << ":" << y << endl;
if (dep[x][1] > dep[y][1])
swap(x, y);
// 令 y 和 x 在一个深度。
int tmp = dep[y][1] - dep[x][1];
for (int j = 0; tmp; ++j, tmp >>= 1)
if (tmp & 1)
y = fa1[y][j];
// cout << x << ":" << y << endl;
// cout << x << ":" << y << endl;
if (y == x)
return x;
// 不然的话,找到第一个不是它们祖先的两个点。
for (int j = 22; j >= 0 && y != x; --j) {
if (fa1[x][j] != fa1[y][j]) {
x = fa1[x][j];
y = fa1[y][j];
}
}
x = fa1[x][0];
// 返回结果。
return x;
}
int lca2(int x, int y) {
// 令 y 比 x 深。
// cout << x << ":" << y << endl;
// cout << dep[x][1] << ":" << dep[y][1] << endl;
if (dep[x][2] > dep[y][2])
swap(x, y);
// 令 y 和 x 在一个深度。
int tmp = dep[y][2] - dep[x][2];
for (int j = 0; tmp; ++j, tmp >>= 1)
if (tmp & 1)
y = fa2[y][j];
// cout << x << ":" << y << endl;
if (y == x)
return x;
// 不然的话,找到第一个不是它们祖先的两个点。
for (int j = 22; j >= 0 && y != x; --j) {
if (fa2[x][j] != fa2[y][j]) {
x = fa2[x][j];
y = fa2[y][j];
}
}
x = fa2[x][0];
// 返回结果。
return x;
}
signed main() {
fastio
// freopen("1.in","r",stdin);
int n,
m, ans = 1e18;
cin >> n >> m;
memset(dis, 127, sizeof(dis));
for (int i = 1, u, v, w; i <= m; i++) {
cin >> u >> v >> w;
e[u].pb({ v, w });
e[v].pb({ u, w });
}
dijsktra(1, 1);
dijsktra(n, 2);
// for(int i = 1 ; i <= n ; i++ )
// {
// cout << dep[i][1] << " \n"[i == n];
// }
// for(int i = 1 ; i <= n ; i++ )
// {
// cout << dep[i][2] << " \n"[i == n];
// }
for (int i = 1; i <= n; i++) {
fa1[i][0] = fa[i][1];
fa2[i][0] = fa[i][2];
}
for (int j = 1; j <= 24; j++) {
for (int i = 1; i <= n; i++) {
fa1[i][j] = fa1[fa1[i][j - 1]][j - 1];
fa2[i][j] = fa2[fa2[i][j - 1]][j - 1];
}
}
for (int j = 0; j <= 3; j++)
// for(int i = 1 ; i <= n ; i++ )
// {
// cout << fa1[i][j] << " \n"[i == n];
// }
for (int x = 1; x <= n; x++) {
for (int y = 1; y <= n; y++) {
if (x == y)
continue;
int l1 = lca1(x, y);
int l2 = lca2(x, y);
// debug(x);
// debug(y);
// debug(l1);
// debug(l2);
if ((l1 == x || l1 == y) && (l2 == x || l2 == y)) {
continue;
}
int cnt = dis[x][1] + dis[y][1] - dis[l1][1] + dis[x][2] + dis[y][2] - dis[l2][2];
// test(dis[x][1] , dis[y][1] , dis[l1][1] , dis[x][2] , dis[y][2] , dis[l2][2]);
ans = min(ans, cnt);
}
}
cout << ans << "\n";
return 0;
}
用户输出
8
系统信息
Exited with return code 0
用户输出
8
系统信息
Exited with return code 0
50 100
1 2 331
2 3 423
3 4 831
3 5 196
2 6 467
4 7 841
5 8 589
6 9 930
9 10 481
3 11 293
7 12 968
5
<852 bytes omitted>
用户输出
1245
Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0
50 100
1 2 37
2 3 90
3 4 270
1 5 616
4 6 462
6 7 801
5 8 922
8 9 701
5 10 204
7 11 330
1 12 588
6 13
<840 bytes omitted>
用户输出
1466
Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0
942 9498
1 2 87293
1 3 92214
3 4 20834
3 5 924
4 6 71171
6 7 66669
6 8 57264
6 9 98803
5 10 52661
7
<129920 bytes omitted>
用户输出
177299
Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0
954 9620
1 2 48928
1 3 77602
2 4 9736
2 5 82149
1 6 14100
2 7 73201
7 8 31260
7 9 82801
2 10 69933
6
<131587 bytes omitted>
用户输出
165534
Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0
946 9136
1 2 3322
1 3 76072
1 4 16527
2 5 9562
5 6 60762
6 7 67224
1 8 88909
7 9 91358
9 10 25363
4
<124859 bytes omitted>
用户输出
161361
Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0
963 9814
1 2 14048
2 3 40980
2 4 76354
1 5 32242
5 6 57710
4 7 74690
3 8 696
2 9 93547
5 10 83686
3
<134310 bytes omitted>
用户输出
172775
Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0
907 9592
1 2 56498
2 3 39992
1 4 97777
3 5 43535
1 6 60669
3 7 8684
6 8 8342
5 9 3341
5 10 54069
3 1
<131170 bytes omitted>
用户输出
140967
Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0
961 9738
1 2 77603
1 3 55107
2 4 94838
1 5 86873
2 6 71895
4 7 42417
7 8 18633
3 9 50720
2 10 8124
2
<133328 bytes omitted>
用户输出
204696
Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0
922 9495
1 2 74386
1 3 46842
1 4 45986
3 5 28221
4 6 813
6 7 9673
5 8 84925
5 9 27070
1 10 28158
6 1
<129894 bytes omitted>
用户输出
165646
Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0
969 9940
1 2 52898
2 3 66949
1 4 33891
1 5 89883
3 6 58933
1 7 43115
6 8 705
1 9 11964
2 10 27082
7
<136015 bytes omitted>
用户输出
144612
Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0
958 9208
1 2 6355
1 3 33442
3 4 5708
1 5 82239
5 6 54649
4 7 90055
1 8 96152
8 9 66805
3 10 2693
9 1
<125934 bytes omitted>
用户输出
173737
Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0
1978 9706
1 2 78441
1 3 93204
1 4 34169
4 5 68390
4 6 68610
2 7 4971
2 8 48605
8 9 41970
4 10 67572
<143038 bytes omitted>
用户输出
142848
Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0
1988 9915
1 2 18876
2 3 50319
2 4 23783
3 5 12278
5 6 52624
2 7 94109
6 8 45323
7 9 85178
3 10 40196
<146223 bytes omitted>
用户输出
120199
Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0
1992 9832
1 2 8550
2 3 74022
2 4 32107
2 5 35012
1 6 63629
4 7 68299
4 8 32176
2 9 52376
7 10 37712
<145210 bytes omitted>
用户输出
349139
Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0
1904 9599
1 2 38275
1 3 8569
2 4 22406
4 5 52940
5 6 90205
4 7 65298
7 8 98943
5 9 69325
6 10 47027
<141327 bytes omitted>
用户输出
498887
Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0
1966 9554
1 2 17891
2 3 8060
3 4 6259
1 5 33026
5 6 71923
6 7 60286
6 8 54211
4 9 29160
9 10 31533
4
<141078 bytes omitted>
用户输出
843451
Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0