用户输出
26
系统信息
Exited with return code 0| 编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
|---|---|---|---|---|---|---|---|---|
| #88868 | #1388. 莉可莉丝 | Accepted | 100 | 6104 ms | 31808 K | C++ 17 / 2.1 K | ONE | 2023-05-13 16:47:16 |
#include <bits/stdc++.h>
#define int unsigned int
#define INF 1e9
using namespace std;
using ll = long long;
const int N = 2e3 + 7;
struct node {
int u, dis, type;
};
bool operator>(const node &x, const node &y) { return x.dis > y.dis; }
struct edge {
int v, w;
};
vector<edge> g[N];
int n, m;
int dis[N][N][2];
bool vis[N][2];
void SP(int S, int dis[N][2]) {
memset(dis, 0x3f, sizeof(int) * N * 2);
dis[S][0] = 0;
for (int i = 1; i <= n; ++i) {
int u = i;
if (dis[u][0] >= INF)
continue;
for (auto [v, w] : g[u]) {
int val = dis[u][0] + w;
if (val < dis[v][0]) {
dis[v][1] = dis[v][0];
dis[v][0] = val;
} else
dis[v][1] = min(dis[v][1], val);
}
}
}
void dijkstra(int S, int dis[N][2]) {
memset(dis, 0x3f, sizeof(int) * N * 2);
memset(vis, 0, sizeof(vis));
priority_queue<node, vector<node>, greater<node>> que;
que.push({ S, 0, 0 });
dis[S][0] = 0;
while (que.size()) {
auto t = que.top();
que.pop();
int u = t.u, type = t.type, distance = t.dis;
if (vis[u][type])
continue;
vis[u][type] = 1;
for (auto ed : g[u]) {
int v = ed.v, w = ed.w;
if (dis[v][0] > distance + w) {
dis[v][1] = dis[v][0];
que.push({ v, dis[v][1], 1 });
dis[v][0] = distance + w;
que.push({ v, dis[v][0], 0 });
} else if (dis[v][1] > distance + w) {
dis[v][1] = distance + w;
que.push({ v, dis[v][1], 1 });
}
}
}
}
void solve() {
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({ v, w });
}
for (int i = 1; i <= n; ++i) dijkstra(i, dis[i]);
// for (int i = 1; i <= n; i++) {
// cout << "dist[1][" << i << "] = " << dis[1][i][0] << endl;
// cout << "dist[1][" << i << "] = " << dis[1][i][1] << endl;
// }
int ans = 1e9;
for (int u = 1; u <= n; ++u)
for (int v = 1; v <= n; ++v)
ans = min(ans, dis[1][u][0] + dis[v][n][0] + dis[u][v][1] + dis[u][v][0]);
cout << ans << "\n";
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
solve();
}用户输出
8
系统信息
Exited with return code 0用户输出
8
系统信息
Exited with return code 050 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>用户输出
4204
系统信息
Exited with return code 050 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>用户输出
1685
系统信息
Exited with return code 0942 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>用户输出
214920
系统信息
Exited with return code 0954 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>用户输出
184919
系统信息
Exited with return code 0946 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>用户输出
191259
系统信息
Exited with return code 0963 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>用户输出
191404
系统信息
Exited with return code 0907 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>用户输出
159164
系统信息
Exited with return code 0961 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>用户输出
226759
系统信息
Exited with return code 0922 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>用户输出
206120
系统信息
Exited with return code 0969 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>用户输出
180825
系统信息
Exited with return code 0958 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>用户输出
201075
系统信息
Exited with return code 01978 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>用户输出
235715
系统信息
Exited with return code 01988 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>用户输出
180635
系统信息
Exited with return code 01992 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>用户输出
400566
系统信息
Exited with return code 01904 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>用户输出
553323
系统信息
Exited with return code 01966 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>用户输出
893510
系统信息
Exited with return code 0