#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <math.h>
#include <cmath>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
#include <random>
#include <deque>
#include <bitset>
#include <string>
#include <queue>
#include <complex>
//#define int long long
#define mp(a, b) make_pair(a, b)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
mt19937 mrand(random_device{}());
double PI = acos((double)-1);
const double eps = 1e-8;
const ll inf0 = 1023 * 1024 * 1024;
const ll inf = inf0 * inf0;
//const ll mod = 1e9 + 7;
//const ll mod = 777777773;
const ll mod = 1e9 + 7;
const ll MOD = mod * mod;
void solve();
void scan();
signed main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
cout << fixed; cout.precision(15);
solve();
}
struct Edge {
int u, v;
ll c, d;
int i;
Edge() {}
Edge(int i, int u, int v, ll c, ll d) : u(u), v(v), c(c), d(d), i(i){}
};
const int N = 201;
vector<Edge> g[N];
ll d1[N], d2[N];
bool used[N];
void djikstra(int s, ll* d) {
for (int i = 0; i < N; i++)
d[i] = inf;
d[s] = 0;
fill(used, used + N, false);
for (int i = 0; i < N; i++) {
int v = -1;
for (int j = 0; j < N; j++) {
if (!used[j] && (v == -1 || d[j] < d[v]))
v = j;
}
used[v] = true;
if (d[v] == inf) break;
for (auto e : g[v]) {
if (d[e.v] > d[v] + e.c) {
d[e.v] = d[v] + e.c;
}
}
}
}
ll jopa[N][N];
void solve() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) jopa[i][j] = 0;
else jopa[i][j] = inf;
}
}
vector<Edge> ed(m);
for (int i = 0; i < m; i++) {
cin >> ed[i].u >> ed[i].v >> ed[i].c >> ed[i].d;
ed[i].u--; ed[i].v--;
jopa[ed[i].u][ed[i].v] = min(jopa[ed[i].u][ed[i].v], ed[i].c);
ed[i].i = i;
g[ed[i].u].push_back(ed[i]);
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (jopa[i][k] != inf && jopa[k][j] != inf && jopa[i][j] > jopa[i][k] + jopa[k][j])
jopa[i][j] = jopa[i][k] + jopa[k][j];
}
}
}
vector<ll> ds1(n, inf), ds2(n, inf);
vector<Edge> p1(n), p2(n);
ds1[0] = 0; ds2[n - 1] = 0;
set<pair<ll, int>> f;
for (int i = 0; i < n; i++)
f.insert({ ds1[i], i });
while (!f.empty()) {
auto v = *f.begin();
if (v.first == inf) break;
f.erase(f.begin());
for (auto e : g[v.second]) {
if (ds1[e.v] > v.first + e.c) {
f.erase({ ds1[e.v], e.v });
p1[e.v] = e;
ds1[e.v] = v.first + e.c;
f.insert({ ds1[e.v], e.v });
}
}
}
f.clear();
for (int i = 0; i < n; i++)
f.insert({ ds2[i], i });
while (!f.empty()) {
auto v = *f.begin();
if (v.first == inf) break;
f.erase(f.begin());
for (auto e : g[v.second]) {
if (ds2[e.v] > v.first + e.c) {
f.erase({ ds2[e.v], e.v });
p2[e.v] = e;
ds2[e.v] = v.first + e.c;
f.insert({ ds2[e.v], e.v });
}
}
}
ll ans = inf;
if (ds1[n - 1] != inf && ds2[0] != inf)
ans = ds1[n - 1] + ds2[0];
vector<int> tmp;
for (int i = 1; i < n; i++)
if(ds1[i] != inf)
tmp.push_back(p1[i].i);
for (int i = 0; i < (n - 1); i++)
if(ds2[i] != inf)
tmp.push_back(p2[i].i);
sort(all(tmp));
tmp.erase(unique(all(tmp)), tmp.end());
vector<bool> cool(m);
for (int j : tmp) {
cool[j] = true;
int h = -1;
//cout << ed[j].i << endl;
for (int k = 0; k < g[ed[j].u].size(); k++) {
if (g[ed[j].u][k].i == ed[j].i) {
h = k;
break;
}
}
g[ed[j].u].erase(g[ed[j].u].begin() + h);
g[ed[j].v].push_back(Edge(ed[j].i, ed[j].v, ed[j].u, ed[j].c, ed[j].d));
djikstra(0, d1);
djikstra(n - 1, d2);
if (d1[n - 1] != inf && d2[0] != inf)
ans = min(ans, d1[n - 1] + d2[0] + ed[j].d);
g[ed[j].u].push_back(ed[j]);
g[ed[j].v].pop_back();
}
for (int i = 0; i < m; i++) {
if (cool[i]) continue;
ll f1 = jopa[0][n - 1];
if (jopa[0][ed[i].v] != inf && jopa[ed[i].u][n - 1] != inf)
f1 = min(f1, jopa[0][ed[i].v] + ed[i].c + jopa[ed[i].u][n - 1]);
ll f2 = jopa[n - 1][0];
if (jopa[n - 1][ed[i].v] != inf && jopa[ed[i].u][0] != inf)
f2 = min(f2, jopa[n - 1][ed[i].v] + ed[i].c + jopa[ed[i].u][0]);
ans = min(ans, f1 + f2 + ed[i].d);
}
if (ans == inf) cout << -1 << endl;
else cout << ans << endl;
return;
}
Compilation message
ho_t4.cpp: In function 'void solve()':
ho_t4.cpp:173:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int k = 0; k < g[ed[j].u].size(); k++) {
~~^~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
61 ms |
760 KB |
Output is correct |
2 |
Correct |
13 ms |
632 KB |
Output is correct |
3 |
Correct |
76 ms |
760 KB |
Output is correct |
4 |
Correct |
79 ms |
760 KB |
Output is correct |
5 |
Correct |
8 ms |
504 KB |
Output is correct |
6 |
Correct |
12 ms |
760 KB |
Output is correct |
7 |
Correct |
5 ms |
376 KB |
Output is correct |
8 |
Correct |
5 ms |
376 KB |
Output is correct |
9 |
Correct |
5 ms |
376 KB |
Output is correct |
10 |
Correct |
63 ms |
760 KB |
Output is correct |
11 |
Correct |
96 ms |
760 KB |
Output is correct |
12 |
Correct |
75 ms |
796 KB |
Output is correct |
13 |
Correct |
35 ms |
760 KB |
Output is correct |
14 |
Correct |
57 ms |
760 KB |
Output is correct |
15 |
Correct |
56 ms |
760 KB |
Output is correct |
16 |
Correct |
50 ms |
760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
146 ms |
4688 KB |
Output is correct |
2 |
Correct |
150 ms |
4728 KB |
Output is correct |
3 |
Correct |
147 ms |
4728 KB |
Output is correct |
4 |
Correct |
70 ms |
888 KB |
Output is correct |
5 |
Correct |
57 ms |
760 KB |
Output is correct |
6 |
Correct |
13 ms |
760 KB |
Output is correct |
7 |
Correct |
13 ms |
760 KB |
Output is correct |
8 |
Correct |
5 ms |
376 KB |
Output is correct |
9 |
Correct |
72 ms |
4600 KB |
Output is correct |
10 |
Correct |
69 ms |
4600 KB |
Output is correct |
11 |
Correct |
110 ms |
4600 KB |
Output is correct |
12 |
Correct |
111 ms |
4600 KB |
Output is correct |
13 |
Correct |
105 ms |
4600 KB |
Output is correct |
14 |
Correct |
96 ms |
4984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
760 KB |
Output is correct |
2 |
Correct |
17 ms |
760 KB |
Output is correct |
3 |
Correct |
139 ms |
3704 KB |
Output is correct |
4 |
Correct |
14 ms |
760 KB |
Output is correct |
5 |
Correct |
153 ms |
4472 KB |
Output is correct |
6 |
Correct |
5 ms |
376 KB |
Output is correct |
7 |
Correct |
5 ms |
376 KB |
Output is correct |
8 |
Correct |
71 ms |
4472 KB |
Output is correct |
9 |
Correct |
85 ms |
4728 KB |
Output is correct |
10 |
Correct |
112 ms |
4600 KB |
Output is correct |
11 |
Correct |
109 ms |
4600 KB |
Output is correct |
12 |
Correct |
114 ms |
4600 KB |
Output is correct |
13 |
Correct |
5 ms |
376 KB |
Output is correct |
14 |
Correct |
5 ms |
376 KB |
Output is correct |
15 |
Correct |
5 ms |
376 KB |
Output is correct |
16 |
Correct |
5 ms |
376 KB |
Output is correct |
17 |
Correct |
5 ms |
376 KB |
Output is correct |
18 |
Correct |
5 ms |
376 KB |
Output is correct |
19 |
Correct |
117 ms |
4728 KB |
Output is correct |
20 |
Correct |
107 ms |
4472 KB |
Output is correct |
21 |
Correct |
121 ms |
4856 KB |
Output is correct |
22 |
Correct |
112 ms |
4600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
61 ms |
760 KB |
Output is correct |
2 |
Correct |
13 ms |
632 KB |
Output is correct |
3 |
Correct |
76 ms |
760 KB |
Output is correct |
4 |
Correct |
79 ms |
760 KB |
Output is correct |
5 |
Correct |
8 ms |
504 KB |
Output is correct |
6 |
Correct |
12 ms |
760 KB |
Output is correct |
7 |
Correct |
5 ms |
376 KB |
Output is correct |
8 |
Correct |
5 ms |
376 KB |
Output is correct |
9 |
Correct |
5 ms |
376 KB |
Output is correct |
10 |
Correct |
63 ms |
760 KB |
Output is correct |
11 |
Correct |
96 ms |
760 KB |
Output is correct |
12 |
Correct |
75 ms |
796 KB |
Output is correct |
13 |
Correct |
35 ms |
760 KB |
Output is correct |
14 |
Correct |
57 ms |
760 KB |
Output is correct |
15 |
Correct |
56 ms |
760 KB |
Output is correct |
16 |
Correct |
50 ms |
760 KB |
Output is correct |
17 |
Correct |
146 ms |
4688 KB |
Output is correct |
18 |
Correct |
150 ms |
4728 KB |
Output is correct |
19 |
Correct |
147 ms |
4728 KB |
Output is correct |
20 |
Correct |
70 ms |
888 KB |
Output is correct |
21 |
Correct |
57 ms |
760 KB |
Output is correct |
22 |
Correct |
13 ms |
760 KB |
Output is correct |
23 |
Correct |
13 ms |
760 KB |
Output is correct |
24 |
Correct |
5 ms |
376 KB |
Output is correct |
25 |
Correct |
72 ms |
4600 KB |
Output is correct |
26 |
Correct |
69 ms |
4600 KB |
Output is correct |
27 |
Correct |
110 ms |
4600 KB |
Output is correct |
28 |
Correct |
111 ms |
4600 KB |
Output is correct |
29 |
Correct |
105 ms |
4600 KB |
Output is correct |
30 |
Correct |
96 ms |
4984 KB |
Output is correct |
31 |
Correct |
62 ms |
760 KB |
Output is correct |
32 |
Correct |
17 ms |
760 KB |
Output is correct |
33 |
Correct |
139 ms |
3704 KB |
Output is correct |
34 |
Correct |
14 ms |
760 KB |
Output is correct |
35 |
Correct |
153 ms |
4472 KB |
Output is correct |
36 |
Correct |
5 ms |
376 KB |
Output is correct |
37 |
Correct |
5 ms |
376 KB |
Output is correct |
38 |
Correct |
71 ms |
4472 KB |
Output is correct |
39 |
Correct |
85 ms |
4728 KB |
Output is correct |
40 |
Correct |
112 ms |
4600 KB |
Output is correct |
41 |
Correct |
109 ms |
4600 KB |
Output is correct |
42 |
Correct |
114 ms |
4600 KB |
Output is correct |
43 |
Correct |
5 ms |
376 KB |
Output is correct |
44 |
Correct |
5 ms |
376 KB |
Output is correct |
45 |
Correct |
5 ms |
376 KB |
Output is correct |
46 |
Correct |
5 ms |
376 KB |
Output is correct |
47 |
Correct |
5 ms |
376 KB |
Output is correct |
48 |
Correct |
5 ms |
376 KB |
Output is correct |
49 |
Correct |
117 ms |
4728 KB |
Output is correct |
50 |
Correct |
107 ms |
4472 KB |
Output is correct |
51 |
Correct |
121 ms |
4856 KB |
Output is correct |
52 |
Correct |
112 ms |
4600 KB |
Output is correct |
53 |
Correct |
132 ms |
4524 KB |
Output is correct |
54 |
Correct |
146 ms |
4600 KB |
Output is correct |
55 |
Correct |
143 ms |
4688 KB |
Output is correct |
56 |
Correct |
86 ms |
764 KB |
Output is correct |
57 |
Correct |
70 ms |
760 KB |
Output is correct |
58 |
Correct |
101 ms |
3704 KB |
Output is correct |
59 |
Correct |
114 ms |
3704 KB |
Output is correct |
60 |
Correct |
141 ms |
3708 KB |
Output is correct |
61 |
Correct |
100 ms |
3704 KB |
Output is correct |
62 |
Correct |
114 ms |
3704 KB |
Output is correct |
63 |
Correct |
142 ms |
3704 KB |
Output is correct |
64 |
Correct |
160 ms |
3704 KB |
Output is correct |
65 |
Correct |
163 ms |
3832 KB |
Output is correct |
66 |
Correct |
204 ms |
3832 KB |
Output is correct |
67 |
Correct |
22 ms |
3568 KB |
Output is correct |
68 |
Correct |
70 ms |
4732 KB |
Output is correct |
69 |
Correct |
69 ms |
4728 KB |
Output is correct |
70 |
Correct |
112 ms |
4600 KB |
Output is correct |
71 |
Correct |
110 ms |
4600 KB |
Output is correct |
72 |
Correct |
121 ms |
4600 KB |
Output is correct |
73 |
Correct |
115 ms |
4728 KB |
Output is correct |
74 |
Correct |
110 ms |
4728 KB |
Output is correct |