#include <bits/stdc++.h>
using namespace std;
const int k_N = 200 + 3;
const int k_M = 5e4 + 3;
const long long k_Inf = 1e17;
int n, m;
long long dist[k_N][k_N];
array<int, 4> edges[k_M];
vector<array<int, 3>> adj[k_N], adj_rev[k_N];
long long d[k_N];
bool in_q[k_N];
bool f1_[k_M], f_n[k_M], f_1[k_M], fn_[k_M];
int par_edge[k_N];
void spfa(int from, int forbidden_idx, vector<array<int, 3>> *adj){
queue<int> q;
for(int i = 1; i <= n; ++i){
d[i] = k_Inf;
in_q[i] = false;
par_edge[i] = -1;
}
d[from] = 0;
q.push(from);
in_q[from] = true;
while(!q.empty()){
int u = q.front();
q.pop();
in_q[u] = false;
for(auto [to, cost, idx]: adj[u]){
if(idx == forbidden_idx) continue;
long long new_d = d[u] + cost;
if(new_d < d[to]){
d[to] = new_d;
par_edge[to] = idx;
if(!in_q[to]){
q.push(to);
in_q[to] = true;
}
}
}
}
}
void do_spfa(int from, bool rev, bool *arr){
if(!rev) spfa(from, -1, adj);
else spfa(from, -1, adj_rev);
for(int i = 1; i <= n; ++i)
if(par_edge[i] != -1)
arr[par_edge[i]] = true;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
dist[i][j] = (i == j) ? 0 : k_Inf;
for(int i = 0; i < m; ++i){
array<int, 4> &e = edges[i];
for(int j = 0; j < 4; ++j)
cin >> e[j];
dist[e[0]][e[1]] = min(dist[e[0]][e[1]], (long long)e[2]);
adj[e[0]].push_back({e[1], e[2], i});
adj_rev[e[1]].push_back({e[0], e[2], i});
}
do_spfa(1, false, f1_);
do_spfa(1, true, f_1);
do_spfa(n, false, fn_);
do_spfa(n, true, f_n);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
for(int k = 1; k <= n; ++k)
if(dist[j][i] + dist[i][k] < dist[j][k])
dist[j][k] = dist[j][i] + dist[i][k];
long long ans = k_Inf;
ans = min(ans, dist[1][n] + dist[n][1]);
for(int i = 0; i < m; ++i){
auto [a, b, c, dd] = edges[i];
long long curr = k_Inf;
long long _1n, _n1, _1b, _an, _nb, _a1;
if(f1_[i]){
spfa(1, i, adj);
_1n = d[n];
_1b = d[b];
}
else{
_1n = dist[1][n];
_1b = dist[1][b];
}
if(fn_[i]){
spfa(n, i, adj);
_n1 = d[1];
_nb = d[b];
}
else{
_n1 = dist[n][1];
_nb = dist[n][b];
}
if(f_n[i]){
spfa(n, i, adj_rev);
_an = d[a];
}
else _an = dist[a][n];
if(f_1[i]){
spfa(1, i, adj_rev);
_a1 = d[a];
}
else _a1 = dist[a][1];
curr = min(curr, _1n + _nb + _a1 + c + dd);
curr = min(curr, _n1 + _1b + _an + c + dd);
curr = min(curr, _nb + _a1 + c + _1b + _an + c + dd);
//cout << curr << " - " << i << endl;
ans = min(ans, curr);
}
if(ans == k_Inf) ans = -1;
cout << ans << "\n";
}
Compilation message
ho_t4.cpp: In function 'void spfa(int, int, std::vector<std::array<int, 3> >*)':
ho_t4.cpp:38:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
for(auto [to, cost, idx]: adj[u]){
^
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:97:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
auto [a, b, c, dd] = edges[i];
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
768 KB |
Output is correct |
2 |
Correct |
9 ms |
640 KB |
Output is correct |
3 |
Correct |
20 ms |
768 KB |
Output is correct |
4 |
Correct |
21 ms |
768 KB |
Output is correct |
5 |
Correct |
2 ms |
512 KB |
Output is correct |
6 |
Correct |
8 ms |
640 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
49 ms |
768 KB |
Output is correct |
11 |
Correct |
53 ms |
768 KB |
Output is correct |
12 |
Correct |
51 ms |
768 KB |
Output is correct |
13 |
Correct |
11 ms |
768 KB |
Output is correct |
14 |
Correct |
15 ms |
768 KB |
Output is correct |
15 |
Correct |
15 ms |
768 KB |
Output is correct |
16 |
Correct |
16 ms |
768 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
256 ms |
3576 KB |
Output is correct |
2 |
Correct |
241 ms |
3584 KB |
Output is correct |
3 |
Correct |
284 ms |
3576 KB |
Output is correct |
4 |
Correct |
24 ms |
768 KB |
Output is correct |
5 |
Correct |
15 ms |
768 KB |
Output is correct |
6 |
Correct |
9 ms |
768 KB |
Output is correct |
7 |
Correct |
8 ms |
640 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
65 ms |
3456 KB |
Output is correct |
10 |
Correct |
64 ms |
3456 KB |
Output is correct |
11 |
Correct |
185 ms |
3584 KB |
Output is correct |
12 |
Correct |
174 ms |
3704 KB |
Output is correct |
13 |
Correct |
189 ms |
3704 KB |
Output is correct |
14 |
Correct |
199 ms |
3960 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
768 KB |
Output is correct |
2 |
Correct |
8 ms |
640 KB |
Output is correct |
3 |
Correct |
92 ms |
2816 KB |
Output is correct |
4 |
Correct |
8 ms |
640 KB |
Output is correct |
5 |
Correct |
110 ms |
3448 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
46 ms |
3456 KB |
Output is correct |
9 |
Correct |
54 ms |
3448 KB |
Output is correct |
10 |
Correct |
94 ms |
3576 KB |
Output is correct |
11 |
Correct |
86 ms |
3704 KB |
Output is correct |
12 |
Correct |
87 ms |
3584 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
0 ms |
384 KB |
Output is correct |
15 |
Correct |
0 ms |
384 KB |
Output is correct |
16 |
Correct |
0 ms |
384 KB |
Output is correct |
17 |
Correct |
0 ms |
384 KB |
Output is correct |
18 |
Correct |
0 ms |
384 KB |
Output is correct |
19 |
Correct |
79 ms |
3832 KB |
Output is correct |
20 |
Correct |
82 ms |
3704 KB |
Output is correct |
21 |
Correct |
81 ms |
3584 KB |
Output is correct |
22 |
Correct |
81 ms |
3576 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
768 KB |
Output is correct |
2 |
Correct |
9 ms |
640 KB |
Output is correct |
3 |
Correct |
20 ms |
768 KB |
Output is correct |
4 |
Correct |
21 ms |
768 KB |
Output is correct |
5 |
Correct |
2 ms |
512 KB |
Output is correct |
6 |
Correct |
8 ms |
640 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
49 ms |
768 KB |
Output is correct |
11 |
Correct |
53 ms |
768 KB |
Output is correct |
12 |
Correct |
51 ms |
768 KB |
Output is correct |
13 |
Correct |
11 ms |
768 KB |
Output is correct |
14 |
Correct |
15 ms |
768 KB |
Output is correct |
15 |
Correct |
15 ms |
768 KB |
Output is correct |
16 |
Correct |
16 ms |
768 KB |
Output is correct |
17 |
Correct |
256 ms |
3576 KB |
Output is correct |
18 |
Correct |
241 ms |
3584 KB |
Output is correct |
19 |
Correct |
284 ms |
3576 KB |
Output is correct |
20 |
Correct |
24 ms |
768 KB |
Output is correct |
21 |
Correct |
15 ms |
768 KB |
Output is correct |
22 |
Correct |
9 ms |
768 KB |
Output is correct |
23 |
Correct |
8 ms |
640 KB |
Output is correct |
24 |
Correct |
0 ms |
384 KB |
Output is correct |
25 |
Correct |
65 ms |
3456 KB |
Output is correct |
26 |
Correct |
64 ms |
3456 KB |
Output is correct |
27 |
Correct |
185 ms |
3584 KB |
Output is correct |
28 |
Correct |
174 ms |
3704 KB |
Output is correct |
29 |
Correct |
189 ms |
3704 KB |
Output is correct |
30 |
Correct |
199 ms |
3960 KB |
Output is correct |
31 |
Correct |
17 ms |
768 KB |
Output is correct |
32 |
Correct |
8 ms |
640 KB |
Output is correct |
33 |
Correct |
92 ms |
2816 KB |
Output is correct |
34 |
Correct |
8 ms |
640 KB |
Output is correct |
35 |
Correct |
110 ms |
3448 KB |
Output is correct |
36 |
Correct |
0 ms |
384 KB |
Output is correct |
37 |
Correct |
0 ms |
384 KB |
Output is correct |
38 |
Correct |
46 ms |
3456 KB |
Output is correct |
39 |
Correct |
54 ms |
3448 KB |
Output is correct |
40 |
Correct |
94 ms |
3576 KB |
Output is correct |
41 |
Correct |
86 ms |
3704 KB |
Output is correct |
42 |
Correct |
87 ms |
3584 KB |
Output is correct |
43 |
Correct |
0 ms |
384 KB |
Output is correct |
44 |
Correct |
0 ms |
384 KB |
Output is correct |
45 |
Correct |
0 ms |
384 KB |
Output is correct |
46 |
Correct |
0 ms |
384 KB |
Output is correct |
47 |
Correct |
0 ms |
384 KB |
Output is correct |
48 |
Correct |
0 ms |
384 KB |
Output is correct |
49 |
Correct |
79 ms |
3832 KB |
Output is correct |
50 |
Correct |
82 ms |
3704 KB |
Output is correct |
51 |
Correct |
81 ms |
3584 KB |
Output is correct |
52 |
Correct |
81 ms |
3576 KB |
Output is correct |
53 |
Correct |
256 ms |
3488 KB |
Output is correct |
54 |
Correct |
228 ms |
3572 KB |
Output is correct |
55 |
Correct |
234 ms |
3448 KB |
Output is correct |
56 |
Correct |
21 ms |
768 KB |
Output is correct |
57 |
Correct |
20 ms |
896 KB |
Output is correct |
58 |
Correct |
427 ms |
2936 KB |
Output is correct |
59 |
Correct |
496 ms |
2836 KB |
Output is correct |
60 |
Correct |
519 ms |
2936 KB |
Output is correct |
61 |
Correct |
380 ms |
2808 KB |
Output is correct |
62 |
Correct |
441 ms |
2816 KB |
Output is correct |
63 |
Correct |
474 ms |
2936 KB |
Output is correct |
64 |
Execution timed out |
1093 ms |
3708 KB |
Time limit exceeded |
65 |
Halted |
0 ms |
0 KB |
- |