#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 = 407;
vector<Edge> g[N];
ll d1[N], d2[N];
void djikstra(int s, ll* d) {
for (int i = 0; i < N; i++)
d[i] = inf;
d[s] = 0;
set<pair<ll, int>> f;
for (int i = 0; i < N; i++)
f.insert({ d[i], i });
while (!f.empty()) {
auto v = *f.begin();
f.erase(f.begin());
if (v.first == inf) break;
for (auto e : g[v.second]) {
if (d[e.v] > v.first + e.c) {
f.erase({ d[e.v],e.v });
d[e.v] = v.first + e.c;
f.insert({ d[e.v],e.v });
}
}
}
}
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:171:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int k = 0; k < g[ed[j].u].size(); k++) {
~~^~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
61 ms |
1144 KB |
Output is correct |
2 |
Correct |
12 ms |
1016 KB |
Output is correct |
3 |
Correct |
91 ms |
1144 KB |
Output is correct |
4 |
Correct |
95 ms |
1272 KB |
Output is correct |
5 |
Correct |
12 ms |
632 KB |
Output is correct |
6 |
Correct |
14 ms |
1144 KB |
Output is correct |
7 |
Correct |
5 ms |
380 KB |
Output is correct |
8 |
Correct |
5 ms |
380 KB |
Output is correct |
9 |
Correct |
5 ms |
504 KB |
Output is correct |
10 |
Correct |
81 ms |
1144 KB |
Output is correct |
11 |
Correct |
103 ms |
1400 KB |
Output is correct |
12 |
Correct |
118 ms |
1144 KB |
Output is correct |
13 |
Correct |
40 ms |
1144 KB |
Output is correct |
14 |
Correct |
68 ms |
1184 KB |
Output is correct |
15 |
Correct |
74 ms |
1144 KB |
Output is correct |
16 |
Correct |
69 ms |
1272 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
269 ms |
5012 KB |
Output is correct |
2 |
Correct |
261 ms |
5116 KB |
Output is correct |
3 |
Correct |
266 ms |
5172 KB |
Output is correct |
4 |
Correct |
85 ms |
1144 KB |
Output is correct |
5 |
Correct |
59 ms |
1144 KB |
Output is correct |
6 |
Correct |
13 ms |
1016 KB |
Output is correct |
7 |
Correct |
15 ms |
1020 KB |
Output is correct |
8 |
Correct |
5 ms |
376 KB |
Output is correct |
9 |
Correct |
101 ms |
4856 KB |
Output is correct |
10 |
Correct |
92 ms |
4856 KB |
Output is correct |
11 |
Correct |
176 ms |
4984 KB |
Output is correct |
12 |
Correct |
176 ms |
4988 KB |
Output is correct |
13 |
Correct |
166 ms |
4984 KB |
Output is correct |
14 |
Correct |
152 ms |
5240 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
62 ms |
1144 KB |
Output is correct |
2 |
Correct |
25 ms |
1144 KB |
Output is correct |
3 |
Correct |
140 ms |
3960 KB |
Output is correct |
4 |
Correct |
17 ms |
1016 KB |
Output is correct |
5 |
Correct |
151 ms |
4856 KB |
Output is correct |
6 |
Correct |
5 ms |
376 KB |
Output is correct |
7 |
Correct |
5 ms |
376 KB |
Output is correct |
8 |
Correct |
77 ms |
4728 KB |
Output is correct |
9 |
Correct |
83 ms |
5112 KB |
Output is correct |
10 |
Correct |
117 ms |
4856 KB |
Output is correct |
11 |
Correct |
111 ms |
4984 KB |
Output is correct |
12 |
Correct |
118 ms |
4984 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 |
4984 KB |
Output is correct |
20 |
Correct |
120 ms |
4856 KB |
Output is correct |
21 |
Correct |
118 ms |
4984 KB |
Output is correct |
22 |
Correct |
117 ms |
4856 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
61 ms |
1144 KB |
Output is correct |
2 |
Correct |
12 ms |
1016 KB |
Output is correct |
3 |
Correct |
91 ms |
1144 KB |
Output is correct |
4 |
Correct |
95 ms |
1272 KB |
Output is correct |
5 |
Correct |
12 ms |
632 KB |
Output is correct |
6 |
Correct |
14 ms |
1144 KB |
Output is correct |
7 |
Correct |
5 ms |
380 KB |
Output is correct |
8 |
Correct |
5 ms |
380 KB |
Output is correct |
9 |
Correct |
5 ms |
504 KB |
Output is correct |
10 |
Correct |
81 ms |
1144 KB |
Output is correct |
11 |
Correct |
103 ms |
1400 KB |
Output is correct |
12 |
Correct |
118 ms |
1144 KB |
Output is correct |
13 |
Correct |
40 ms |
1144 KB |
Output is correct |
14 |
Correct |
68 ms |
1184 KB |
Output is correct |
15 |
Correct |
74 ms |
1144 KB |
Output is correct |
16 |
Correct |
69 ms |
1272 KB |
Output is correct |
17 |
Correct |
269 ms |
5012 KB |
Output is correct |
18 |
Correct |
261 ms |
5116 KB |
Output is correct |
19 |
Correct |
266 ms |
5172 KB |
Output is correct |
20 |
Correct |
85 ms |
1144 KB |
Output is correct |
21 |
Correct |
59 ms |
1144 KB |
Output is correct |
22 |
Correct |
13 ms |
1016 KB |
Output is correct |
23 |
Correct |
15 ms |
1020 KB |
Output is correct |
24 |
Correct |
5 ms |
376 KB |
Output is correct |
25 |
Correct |
101 ms |
4856 KB |
Output is correct |
26 |
Correct |
92 ms |
4856 KB |
Output is correct |
27 |
Correct |
176 ms |
4984 KB |
Output is correct |
28 |
Correct |
176 ms |
4988 KB |
Output is correct |
29 |
Correct |
166 ms |
4984 KB |
Output is correct |
30 |
Correct |
152 ms |
5240 KB |
Output is correct |
31 |
Correct |
62 ms |
1144 KB |
Output is correct |
32 |
Correct |
25 ms |
1144 KB |
Output is correct |
33 |
Correct |
140 ms |
3960 KB |
Output is correct |
34 |
Correct |
17 ms |
1016 KB |
Output is correct |
35 |
Correct |
151 ms |
4856 KB |
Output is correct |
36 |
Correct |
5 ms |
376 KB |
Output is correct |
37 |
Correct |
5 ms |
376 KB |
Output is correct |
38 |
Correct |
77 ms |
4728 KB |
Output is correct |
39 |
Correct |
83 ms |
5112 KB |
Output is correct |
40 |
Correct |
117 ms |
4856 KB |
Output is correct |
41 |
Correct |
111 ms |
4984 KB |
Output is correct |
42 |
Correct |
118 ms |
4984 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 |
4984 KB |
Output is correct |
50 |
Correct |
120 ms |
4856 KB |
Output is correct |
51 |
Correct |
118 ms |
4984 KB |
Output is correct |
52 |
Correct |
117 ms |
4856 KB |
Output is correct |
53 |
Correct |
250 ms |
4856 KB |
Output is correct |
54 |
Correct |
275 ms |
5112 KB |
Output is correct |
55 |
Correct |
256 ms |
4856 KB |
Output is correct |
56 |
Correct |
97 ms |
1144 KB |
Output is correct |
57 |
Correct |
88 ms |
1272 KB |
Output is correct |
58 |
Correct |
177 ms |
3960 KB |
Output is correct |
59 |
Correct |
203 ms |
4008 KB |
Output is correct |
60 |
Correct |
287 ms |
4088 KB |
Output is correct |
61 |
Correct |
170 ms |
3960 KB |
Output is correct |
62 |
Correct |
196 ms |
3960 KB |
Output is correct |
63 |
Correct |
274 ms |
3960 KB |
Output is correct |
64 |
Execution timed out |
1099 ms |
4064 KB |
Time limit exceeded |
65 |
Halted |
0 ms |
0 KB |
- |