#include <bits/stdc++.h>
//#undef BALBIT
using namespace std;
#define ll long long
#define int ll
#define y1 zck_is_king
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1e9+10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9+7 ;
void GG(){cout<<"0\n"; exit(0);}
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
ll re=1;
while (n>0){
if (n&1) re = re*a %mo;
a = a*a %mo;
n>>=1;
}
return re;
}
ll inv (ll b, ll mo = mod){
if (b==1) return b;
return (mo-mo/b) * inv(mo%b,mo) % mo;
}
const int maxn = 200+5;
struct edge{
int v, u, w, d, i;
};
vector<edge> g[maxn], gt[maxn];
bool done[maxn], ban[50005];
int par[maxn];
ll d[maxn], rd[maxn];
int n,m;
ll dij(int S, int T, vector<edge> gee[], ll D[]){
// return 3;
assert(D[17] == 0x3f3f3f3f3f3f3f3f);
memset (done, 0, sizeof done);
D[S] = 0;
while (1){
ll w = inf; int v = -1;
REP(i,n) {
if (!done[i]) {
if (D[i] < w) {
w = D[i]; v = i;
}
}
}
if (v == -1) break;
done[v] = 1;
for (edge & e : gee[v]) {
if (e.i!=-1 && ban[e.i]) continue;
if (D[e.u] > D[v] + e.w) {
D[e.u] = D[v] + e.w;
par[e.u] = e.i;
}
}
}
return D[T];
}
vector<edge> E;
ll go(int S = 0, int T = n-1) {
// return -1;
memset(ban, 0, sizeof ban);
memset(par, -1, sizeof par);
memset (d, 0x3f, sizeof d);
ll re = dij(T, S, g, d);
memset (d, 0x3f, sizeof d);
ll straight = dij(S,T, g, d);
re += straight; MN(re, inf);
vector<int> pth;
if (straight < inf){
for (int at = T; par[at] !=-1 && at != S; ) {
bug(par[at]);
pth.pb(par[at]);
// ban[par[at]] = 1;
at = E[par[at]].v;
}
}
// return -1;
bug(straight);
vector<int> tmp(m);
{
memset (d, 0x3f, sizeof d);
memset (rd, 0x3f, sizeof rd);
dij(T, S, gt, rd);
dij(S, T, g, d);
REP(i, m) {
edge &e = E[i];
tmp[i] = e.w + rd[e.v] + d[e.u];
}
}
memset (d, 0x3f, sizeof d);
memset (rd, 0x3f, sizeof rd);
dij(T, S, g, d);
dij(S, T, gt,rd);
for (int x : pth) ban[x] = 1;
int nw = 0;
for (edge &e : E) {
if (!ban[e.i]) {
MN(re, min(inf, min(straight,tmp[nw]) + min(inf, rd[e.v] + d[e.u])) + e.d + e.w);
// if (e.i == 1) {
// bug(e.v, e.u, rd[e.v]+ d[e.u]+ e.d+ e.w + straight);
// }
}
++nw;
// bug(re);
}
memset(ban, 0, sizeof ban);
for (int i : pth) {
// REP(i,m){
edge & e = E[i];
ban[e.i] = 1; g[e.u].pb({e.u, e.v, e.w, e.d, -1});
memset (d, 0x3f, sizeof d);
ll t1 = dij(S,T,g,d);
memset (d, 0x3f, sizeof d);
ll t2 = dij(T,S,g,d);
MN(re, t1+t2+e.d);
g[e.u].pop_back();
ban[e.i] = 0;
}
return re;
}
signed main(){
IOS();
cin>>n>>m;
REP(i,m) {
int a,b,w,p; cin>>a>>b>>w>>p; --a; --b;
E.pb({a,b,w,p,i});
g[a] .pb({a,b,w,p,i});
gt[b].pb({b,a,w,p,i});
}
ll ans = go();
bug(ans);
// swap(g, gt);
// for (edge & e : E) swap(e.v, e.u);
ans = min(ans, go(n-1, 0));
bug(ans);
if (ans > inf/2) ans = -1;
cout<<ans<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
620 KB |
Output is correct |
| 2 |
Correct |
1 ms |
492 KB |
Output is correct |
| 3 |
Correct |
5 ms |
620 KB |
Output is correct |
| 4 |
Correct |
6 ms |
620 KB |
Output is correct |
| 5 |
Correct |
1 ms |
620 KB |
Output is correct |
| 6 |
Correct |
1 ms |
492 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
8844 KB |
Output is correct |
| 2 |
Correct |
34 ms |
8956 KB |
Output is correct |
| 3 |
Correct |
35 ms |
9084 KB |
Output is correct |
| 4 |
Correct |
5 ms |
748 KB |
Output is correct |
| 5 |
Correct |
5 ms |
620 KB |
Output is correct |
| 6 |
Correct |
1 ms |
492 KB |
Output is correct |
| 7 |
Correct |
1 ms |
492 KB |
Output is correct |
| 8 |
Correct |
1 ms |
364 KB |
Output is correct |
| 9 |
Correct |
30 ms |
8572 KB |
Output is correct |
| 10 |
Correct |
30 ms |
9724 KB |
Output is correct |
| 11 |
Correct |
35 ms |
9980 KB |
Output is correct |
| 12 |
Correct |
35 ms |
9724 KB |
Output is correct |
| 13 |
Correct |
36 ms |
9980 KB |
Output is correct |
| 14 |
Correct |
34 ms |
10492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
620 KB |
Output is correct |
| 2 |
Correct |
1 ms |
492 KB |
Output is correct |
| 3 |
Correct |
24 ms |
7424 KB |
Output is correct |
| 4 |
Correct |
1 ms |
492 KB |
Output is correct |
| 5 |
Correct |
30 ms |
8444 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
620 KB |
Output is correct |
| 2 |
Correct |
1 ms |
492 KB |
Output is correct |
| 3 |
Correct |
5 ms |
620 KB |
Output is correct |
| 4 |
Correct |
6 ms |
620 KB |
Output is correct |
| 5 |
Correct |
1 ms |
620 KB |
Output is correct |
| 6 |
Correct |
1 ms |
492 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
