#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<vpl> al;
typedef vector<ll> vl;
typedef pair<pl,pl> egg;
const ll INFL = 1e18;
const int MP = 220;
const int MN = 50500;
al g,h;
vector<vl> ha;
vector<egg> eg;
vl fist,rist;
vl fast,rast;
vl pis, ris;
vl so;
bitset<MN> fs,rs;
bitset<MP> fat,rat;
void dja(vl& w, vl& pa, int s) {
w.assign(g.size(),INFL);
pa.assign(g.size(),-1);
priority_queue<pl,vpl,greater<pl> > pq;
pq.push({0,s});
w[s] = 0;
while(!pq.empty()) {
pl co = pq.top();pq.pop();
int u = co.second;
if(co.first > w[u]) {continue;}
for(int i=0;i<g[u].size();i++) {
int v = g[u][i].first;
ll d = g[u][i].second;
if(d+w[u] < w[v]) {
w[v] = d+w[u];
int e = ha[u][i];
pa[v] = e;
pq.push({w[v],v});
}
}
}
}
void djb(vl& w, al& gr, int s) {
w.assign(gr.size(),INFL);
priority_queue<pl,vpl,greater<pl> > pq;
pq.push({0,s});
w[s] = 0;
while(!pq.empty()) {
pl co = pq.top();pq.pop();
int u = co.second;
if(co.first > w[u]) {continue;}
for(int i=0;i<gr[u].size();i++) {
int v = gr[u][i].first;
ll d = gr[u][i].second;
if(d+w[u] < w[v]) {
w[v] = d+w[u];
pq.push({w[v],v});
}
}
}
}
void pre() {
dja(fist,pis, 0);
dja(rist,ris, g.size()-1);
djb(fast,h,g.size()-1);
djb(rast,h,0);
int pp = g.size()-1;
while(pis[pp] != -1) {
fat.set(pp);
fs.set(pis[pp]);
pp = eg[pis[pp]].first.first;
}
fat.set(0);
for(int i=0;i<ris.size();i++) {
if(ris[i] != -1) {
rs.set(ris[i]);
}
}
pp = 0;
while(ris[pp] != -1) {
rat.set(pp);
rs.set(ris[pp]);
pp = eg[ris[pp]].first.first;
}
rat.set(g.size()-1);
}
ll proc(int e) {
vl tp;
int u = eg[e].first.first;
int v = eg[e].first.second;
ll ex = eg[e].second.second;
ll reg = eg[e].second.first;
int eid = so[e];
ll fdi,rdi;
if(fs[e]) {
g[u][eid].second = INFL;
g[v].push_back({u,reg});
djb(tp,g,0);
fdi = tp[g.size()-1];
g[v].pop_back();
g[u][eid].second = reg;
} else {
fdi = fist[g.size()-1];
fdi = min(fdi,fist[v]+fast[u]+reg);
}
if(rs[e]) {
g[u][eid].second = INFL;
g[v].push_back({u,reg});
djb(tp,g,g.size()-1);
rdi = tp[0];
g[v].pop_back();
g[u][eid].second = reg;
} else {
rdi = rist[0];
rdi = min(rdi,rist[v]+rast[u]+reg);
}
return fdi+rdi+ex;
}
int main() {
ios::sync_with_stdio(0);cin.tie(0);
ll n,m;
cin >> n >> m;
g.assign(n,vpl());
h.assign(n,vpl());
ha.assign(n,vl());
fist.assign(n,INFL);
rist.assign(n,INFL);
for(int i=0;i<m;i++) {
ll a,b,c,d;
cin >> a >> b >> c >> d;
a--;b--;
so.push_back(g[a].size());
g[a].push_back({b,c});
h[b].push_back({a,c});
ha[a].push_back(i);
eg.push_back({{a,b},{c,d}});
}
pre();
ll res = fist[n-1]+rist[0];
for(int i=0;i<m;i++) {
res = min(res,proc(i));
}
if(res >= INFL) {
cout << -1 << '\n';
} else {
cout << res << '\n';
}
}
Compilation message
ho_t4.cpp: In function 'void dja(vl&, vl&, int)':
ho_t4.cpp:31:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[u].size();i++) {
~^~~~~~~~~~~~
ho_t4.cpp: In function 'void djb(vl&, al&, int)':
ho_t4.cpp:52:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<gr[u].size();i++) {
~^~~~~~~~~~~~~
ho_t4.cpp: In function 'void pre()':
ho_t4.cpp:74:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<ris.size();i++) {
~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
512 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
11 ms |
560 KB |
Output is correct |
4 |
Correct |
12 ms |
512 KB |
Output is correct |
5 |
Correct |
6 ms |
512 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
4 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
512 KB |
Output is correct |
10 |
Correct |
22 ms |
512 KB |
Output is correct |
11 |
Correct |
21 ms |
512 KB |
Output is correct |
12 |
Correct |
22 ms |
512 KB |
Output is correct |
13 |
Correct |
6 ms |
512 KB |
Output is correct |
14 |
Correct |
7 ms |
512 KB |
Output is correct |
15 |
Correct |
10 ms |
512 KB |
Output is correct |
16 |
Correct |
7 ms |
512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
68 ms |
6504 KB |
Output is correct |
2 |
Correct |
67 ms |
6512 KB |
Output is correct |
3 |
Correct |
65 ms |
6756 KB |
Output is correct |
4 |
Correct |
10 ms |
640 KB |
Output is correct |
5 |
Correct |
8 ms |
512 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
40 ms |
6632 KB |
Output is correct |
10 |
Correct |
37 ms |
6632 KB |
Output is correct |
11 |
Correct |
67 ms |
6888 KB |
Output is correct |
12 |
Correct |
40 ms |
6640 KB |
Output is correct |
13 |
Correct |
64 ms |
6616 KB |
Output is correct |
14 |
Correct |
65 ms |
7140 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
512 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
45 ms |
5740 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
50 ms |
6376 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
4 ms |
384 KB |
Output is correct |
8 |
Correct |
33 ms |
6512 KB |
Output is correct |
9 |
Correct |
35 ms |
6384 KB |
Output is correct |
10 |
Correct |
36 ms |
6384 KB |
Output is correct |
11 |
Correct |
53 ms |
6376 KB |
Output is correct |
12 |
Correct |
49 ms |
6504 KB |
Output is correct |
13 |
Correct |
5 ms |
384 KB |
Output is correct |
14 |
Correct |
4 ms |
384 KB |
Output is correct |
15 |
Correct |
4 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
512 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
Correct |
5 ms |
384 KB |
Output is correct |
19 |
Correct |
38 ms |
6512 KB |
Output is correct |
20 |
Correct |
52 ms |
6376 KB |
Output is correct |
21 |
Correct |
52 ms |
6384 KB |
Output is correct |
22 |
Correct |
51 ms |
6392 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
512 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
11 ms |
560 KB |
Output is correct |
4 |
Correct |
12 ms |
512 KB |
Output is correct |
5 |
Correct |
6 ms |
512 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
4 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
512 KB |
Output is correct |
10 |
Correct |
22 ms |
512 KB |
Output is correct |
11 |
Correct |
21 ms |
512 KB |
Output is correct |
12 |
Correct |
22 ms |
512 KB |
Output is correct |
13 |
Correct |
6 ms |
512 KB |
Output is correct |
14 |
Correct |
7 ms |
512 KB |
Output is correct |
15 |
Correct |
10 ms |
512 KB |
Output is correct |
16 |
Correct |
7 ms |
512 KB |
Output is correct |
17 |
Correct |
68 ms |
6504 KB |
Output is correct |
18 |
Correct |
67 ms |
6512 KB |
Output is correct |
19 |
Correct |
65 ms |
6756 KB |
Output is correct |
20 |
Correct |
10 ms |
640 KB |
Output is correct |
21 |
Correct |
8 ms |
512 KB |
Output is correct |
22 |
Correct |
5 ms |
384 KB |
Output is correct |
23 |
Correct |
5 ms |
384 KB |
Output is correct |
24 |
Correct |
5 ms |
384 KB |
Output is correct |
25 |
Correct |
40 ms |
6632 KB |
Output is correct |
26 |
Correct |
37 ms |
6632 KB |
Output is correct |
27 |
Correct |
67 ms |
6888 KB |
Output is correct |
28 |
Correct |
40 ms |
6640 KB |
Output is correct |
29 |
Correct |
64 ms |
6616 KB |
Output is correct |
30 |
Correct |
65 ms |
7140 KB |
Output is correct |
31 |
Correct |
10 ms |
512 KB |
Output is correct |
32 |
Correct |
5 ms |
384 KB |
Output is correct |
33 |
Correct |
45 ms |
5740 KB |
Output is correct |
34 |
Correct |
5 ms |
384 KB |
Output is correct |
35 |
Correct |
50 ms |
6376 KB |
Output is correct |
36 |
Correct |
5 ms |
384 KB |
Output is correct |
37 |
Correct |
4 ms |
384 KB |
Output is correct |
38 |
Correct |
33 ms |
6512 KB |
Output is correct |
39 |
Correct |
35 ms |
6384 KB |
Output is correct |
40 |
Correct |
36 ms |
6384 KB |
Output is correct |
41 |
Correct |
53 ms |
6376 KB |
Output is correct |
42 |
Correct |
49 ms |
6504 KB |
Output is correct |
43 |
Correct |
5 ms |
384 KB |
Output is correct |
44 |
Correct |
4 ms |
384 KB |
Output is correct |
45 |
Correct |
4 ms |
384 KB |
Output is correct |
46 |
Correct |
5 ms |
512 KB |
Output is correct |
47 |
Correct |
5 ms |
384 KB |
Output is correct |
48 |
Correct |
5 ms |
384 KB |
Output is correct |
49 |
Correct |
38 ms |
6512 KB |
Output is correct |
50 |
Correct |
52 ms |
6376 KB |
Output is correct |
51 |
Correct |
52 ms |
6384 KB |
Output is correct |
52 |
Correct |
51 ms |
6392 KB |
Output is correct |
53 |
Correct |
70 ms |
6384 KB |
Output is correct |
54 |
Correct |
70 ms |
6372 KB |
Output is correct |
55 |
Correct |
70 ms |
6636 KB |
Output is correct |
56 |
Correct |
11 ms |
512 KB |
Output is correct |
57 |
Correct |
11 ms |
512 KB |
Output is correct |
58 |
Correct |
95 ms |
5876 KB |
Output is correct |
59 |
Correct |
103 ms |
5876 KB |
Output is correct |
60 |
Correct |
103 ms |
5876 KB |
Output is correct |
61 |
Correct |
80 ms |
5868 KB |
Output is correct |
62 |
Correct |
95 ms |
5876 KB |
Output is correct |
63 |
Correct |
104 ms |
5876 KB |
Output is correct |
64 |
Correct |
700 ms |
5876 KB |
Output is correct |
65 |
Correct |
629 ms |
5876 KB |
Output is correct |
66 |
Correct |
596 ms |
5748 KB |
Output is correct |
67 |
Correct |
23 ms |
5468 KB |
Output is correct |
68 |
Correct |
40 ms |
6632 KB |
Output is correct |
69 |
Correct |
37 ms |
6632 KB |
Output is correct |
70 |
Correct |
42 ms |
6640 KB |
Output is correct |
71 |
Correct |
43 ms |
6632 KB |
Output is correct |
72 |
Correct |
68 ms |
6632 KB |
Output is correct |
73 |
Correct |
70 ms |
6768 KB |
Output is correct |
74 |
Correct |
46 ms |
6760 KB |
Output is correct |