#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3 / 100
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())
struct gujo
{
ll V, C, D, num;
};
ll n, m;
ll all, bll, cll, dll;
vector< pair<pll, pll> > edg;
vector<gujo> vec[210], yuk[210];
ll ans[50010];
ll dist[210][2];
ll dist2[50010][210][2];
ll bk[210][2], bk2[210][2];
ll chk[210], chk2[50010];
ll ans2 = INF, ans3;
void dijkstra(ll X)
{
for(ll i = 1 ; i <= n ; i++)
dist[i][0] = INF, bk[i][0] = bk2[i][0] = chk[i] = 0;
dist[1][0] = 0;
for(ll i = 1 ; i <= n ; i++)
{
ll minn = INF, w = -1;
for(ll j = 1 ; j <= n ; j++)
{
if(chk[j])
continue;
if(minn > dist[j][0])
{
minn = dist[j][0];
w = j;
}
}
if(w == -1)
break;
chk[w] = 1;
for(auto &j : vec[w])
{
if(j.num == X)
continue;
if(dist[j.V][0] > dist[w][0] + j.C)
{
dist[j.V][0] = dist[w][0] + j.C;
bk[j.V][0] = w;
bk2[j.V][0] = j.num;
}
}
}
for(ll i = 1 ; i <= n ; i++)
dist[i][1] = INF, bk[i][1] = bk2[i][1] = chk[i] = 0;
dist[n][1] = 0;
for(ll i = 1 ; i <= n ; i++)
{
ll minn = INF, w = -1;
for(ll j = 1 ; j <= n ; j++)
{
if(chk[j])
continue;
if(minn > dist[j][1])
{
minn = dist[j][1];
w = j;
}
}
if(w == -1)
break;
chk[w] = 1;
for(auto &j : yuk[w])
{
if(j.num == X)
continue;
if(dist[j.V][1] > dist[w][1] + j.C)
{
dist[j.V][1] = dist[w][1] + j.C;
bk[j.V][1] = w;
bk2[j.V][1] = j.num;
}
}
}
for(ll i = 1 ; i <= n ; i++)
dist2[X][i][0] = dist[i][0], dist2[X][i][1] = dist[i][1];
}
void solve(void)
{
dijkstra(0);
ans3 += dist2[0][n][0];
vector<ll> path;
for(ll i = n ; i > 0 ; i = bk[i][0])
path.push_back(bk2[i][0]);
for(ll i = 1 ; i <= m ; i++)
chk2[i] = 0;
for(auto &i : path)
{
dijkstra(i);
chk2[i] = 1;
}
for(ll i = 1 ; i <= m ; i++)
{
if(!chk2[i])
ans[i] += min(dist2[0][n][0], dist2[0][edg[i - 1].fi.se][0] + dist2[0][edg[i - 1].fi.fi][1] + edg[i - 1].se.fi);
else
ans[i] += min(dist2[i][n][0], dist2[i][edg[i - 1].fi.se][0] + dist2[i][edg[i - 1].fi.fi][1] + edg[i - 1].se.fi);
}
}
int main(void)
{
fastio
cin >> n >> m;
for(ll i = 1 ; i <= m ; i++)
{
cin >> all >> bll >> cll >> dll;
edg.push_back({{all, bll}, {cll, dll}});
vec[all].push_back({bll, cll, dll, i});
yuk[bll].push_back({all, cll, dll, i});
ans[i] += dll;
}
solve();
for(ll i = 1 ; i <= n ; i++)
{
vec[i].clear();
yuk[i].clear();
}
ll cc = 0;
for(auto &i : edg)
{
if(i.fi.fi == 1)
i.fi.fi = n;
else if(i.fi.fi == n)
i.fi.fi = 1;
if(i.fi.se == 1)
i.fi.se = n;
else if(i.fi.se == n)
i.fi.se = 1;
cc++;
vec[i.fi.fi].push_back({i.fi.se, i.se.fi, i.se.se, cc});
yuk[i.fi.se].push_back({i.fi.fi, i.se.fi, i.se.se, cc});
}
solve();
for(ll i = 1 ; i <= m ; i++)
ans2 = min(ans2, ans[i]);
ans2 = min(ans2, ans3);
if(ans2 >= INF / 10)
cout << -1;
else
cout << ans2;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
724 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
3 ms |
608 KB |
Output is correct |
4 |
Correct |
4 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
596 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
596 KB |
Output is correct |
10 |
Correct |
64 ms |
1780 KB |
Output is correct |
11 |
Correct |
65 ms |
2288 KB |
Output is correct |
12 |
Correct |
65 ms |
2176 KB |
Output is correct |
13 |
Correct |
1 ms |
468 KB |
Output is correct |
14 |
Correct |
3 ms |
596 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
3 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
8644 KB |
Output is correct |
2 |
Correct |
21 ms |
8632 KB |
Output is correct |
3 |
Correct |
21 ms |
8784 KB |
Output is correct |
4 |
Correct |
3 ms |
732 KB |
Output is correct |
5 |
Correct |
4 ms |
596 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
19 ms |
8616 KB |
Output is correct |
10 |
Correct |
19 ms |
8912 KB |
Output is correct |
11 |
Correct |
22 ms |
8796 KB |
Output is correct |
12 |
Correct |
21 ms |
8968 KB |
Output is correct |
13 |
Correct |
22 ms |
8652 KB |
Output is correct |
14 |
Correct |
28 ms |
9376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
14 ms |
6920 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
18 ms |
8448 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
18 ms |
8344 KB |
Output is correct |
9 |
Correct |
17 ms |
8636 KB |
Output is correct |
10 |
Correct |
21 ms |
8540 KB |
Output is correct |
11 |
Correct |
17 ms |
8444 KB |
Output is correct |
12 |
Correct |
18 ms |
8500 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
18 ms |
8756 KB |
Output is correct |
20 |
Correct |
18 ms |
8436 KB |
Output is correct |
21 |
Correct |
18 ms |
8412 KB |
Output is correct |
22 |
Correct |
18 ms |
8464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
724 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
3 ms |
608 KB |
Output is correct |
4 |
Correct |
4 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
596 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
596 KB |
Output is correct |
10 |
Correct |
64 ms |
1780 KB |
Output is correct |
11 |
Correct |
65 ms |
2288 KB |
Output is correct |
12 |
Correct |
65 ms |
2176 KB |
Output is correct |
13 |
Correct |
1 ms |
468 KB |
Output is correct |
14 |
Correct |
3 ms |
596 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
3 ms |
596 KB |
Output is correct |
17 |
Correct |
21 ms |
8644 KB |
Output is correct |
18 |
Correct |
21 ms |
8632 KB |
Output is correct |
19 |
Correct |
21 ms |
8784 KB |
Output is correct |
20 |
Correct |
3 ms |
732 KB |
Output is correct |
21 |
Correct |
4 ms |
596 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
344 KB |
Output is correct |
24 |
Correct |
0 ms |
340 KB |
Output is correct |
25 |
Correct |
19 ms |
8616 KB |
Output is correct |
26 |
Correct |
19 ms |
8912 KB |
Output is correct |
27 |
Correct |
22 ms |
8796 KB |
Output is correct |
28 |
Correct |
21 ms |
8968 KB |
Output is correct |
29 |
Correct |
22 ms |
8652 KB |
Output is correct |
30 |
Correct |
28 ms |
9376 KB |
Output is correct |
31 |
Correct |
3 ms |
596 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
14 ms |
6920 KB |
Output is correct |
34 |
Correct |
1 ms |
340 KB |
Output is correct |
35 |
Correct |
18 ms |
8448 KB |
Output is correct |
36 |
Correct |
0 ms |
340 KB |
Output is correct |
37 |
Correct |
1 ms |
340 KB |
Output is correct |
38 |
Correct |
18 ms |
8344 KB |
Output is correct |
39 |
Correct |
17 ms |
8636 KB |
Output is correct |
40 |
Correct |
21 ms |
8540 KB |
Output is correct |
41 |
Correct |
17 ms |
8444 KB |
Output is correct |
42 |
Correct |
18 ms |
8500 KB |
Output is correct |
43 |
Correct |
0 ms |
340 KB |
Output is correct |
44 |
Correct |
0 ms |
340 KB |
Output is correct |
45 |
Correct |
1 ms |
340 KB |
Output is correct |
46 |
Correct |
1 ms |
340 KB |
Output is correct |
47 |
Correct |
1 ms |
340 KB |
Output is correct |
48 |
Correct |
1 ms |
340 KB |
Output is correct |
49 |
Correct |
18 ms |
8756 KB |
Output is correct |
50 |
Correct |
18 ms |
8436 KB |
Output is correct |
51 |
Correct |
18 ms |
8412 KB |
Output is correct |
52 |
Correct |
18 ms |
8464 KB |
Output is correct |
53 |
Correct |
21 ms |
8388 KB |
Output is correct |
54 |
Correct |
21 ms |
8560 KB |
Output is correct |
55 |
Correct |
21 ms |
8388 KB |
Output is correct |
56 |
Correct |
3 ms |
596 KB |
Output is correct |
57 |
Correct |
3 ms |
592 KB |
Output is correct |
58 |
Correct |
112 ms |
8368 KB |
Output is correct |
59 |
Correct |
118 ms |
8556 KB |
Output is correct |
60 |
Correct |
113 ms |
9184 KB |
Output is correct |
61 |
Correct |
91 ms |
8324 KB |
Output is correct |
62 |
Correct |
113 ms |
8608 KB |
Output is correct |
63 |
Correct |
114 ms |
9236 KB |
Output is correct |
64 |
Correct |
199 ms |
8524 KB |
Output is correct |
65 |
Correct |
175 ms |
8888 KB |
Output is correct |
66 |
Correct |
158 ms |
9764 KB |
Output is correct |
67 |
Correct |
15 ms |
10160 KB |
Output is correct |
68 |
Correct |
20 ms |
8680 KB |
Output is correct |
69 |
Correct |
18 ms |
8400 KB |
Output is correct |
70 |
Correct |
21 ms |
8676 KB |
Output is correct |
71 |
Correct |
21 ms |
8592 KB |
Output is correct |
72 |
Correct |
20 ms |
8624 KB |
Output is correct |
73 |
Correct |
21 ms |
8764 KB |
Output is correct |
74 |
Correct |
23 ms |
8884 KB |
Output is correct |