#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
const ll inf = 1e18;
struct edge{
ll x, y, z, d, id;
};
edge e[50009];
ll n, m;
ll dis[209][209];
vector<ll> g[209];
ll vis[209];
ll used[50009];
ll prt[209][10];
ll depth[209];
void createtree(ll root){
vis[root] = 1;
for(int i = 0; i < m; ++i)
if(vis[e[i].y] == 0 && dis[root][e[i].y] == dis[root][e[i].x] + e[i].z){
used[i] = 1;
vis[e[i].y] = 1;
g[e[i].x].pb(e[i].y);
}
}
void dfs(ll v, ll p){
prt[v][0] = p;
depth[v] = depth[p]+1;
for(ll i = 1; i < 10; ++i)
prt[v][i] = prt[prt[v][i-1]][i-1];
for(auto u : g[v])
dfs(u, v);
}
int lca(ll x, ll y){
if(depth[y] > depth[x]) swap(x, y);
for(ll i = 9; i >= 0; --i)
if(depth[prt[x][i]] >= depth[y])
x = prt[x][i];
if(x == y) return x;
for(ll i = 9; i >= 0; --i)
if(prt[x][i] != prt[y][i]){
x = prt[x][i];
y = prt[y][i];
}
return prt[x][0];
}
void addto(pll x, set<pll> &s){
auto it = s.lower_bound(x);
if(it != s.begin()){
--it;
if((*it).ss <= x.ss)
return;
}
s.insert(x);
while(1){
it = s.upper_bound(x);
if(it == s.end() || (*it).ss < x.ss) break;
s.erase(it);
}
}
ll ans[50009];
set<pll> alt[209];
vector<edge> inc[209];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
cin >> n >> m;
for(ll i = 1; i <= n; ++i)
for(ll j = 1; j <= n; ++j)
if(i != j)
dis[i][j] = inf;
for(ll i = 0; i < m; ++i){
cin >> e[i].x >> e[i].y >> e[i].z >> e[i].d;
e[i].id = i;
dis[e[i].x][e[i].y] = min(dis[e[i].x][e[i].y], e[i].z);
ans[i] = e[i].d;
inc[e[i].y].pb(e[i]);
}
for(ll k = 1; k <= n; ++k)
for(ll i = 1; i <= n; ++i)
for(ll j = 1; j <= n; ++j)
dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
createtree(1);
dfs(1, 0);
for(ll i = 0; i < m; ++i){
if(used[i] == 1) continue;
if(vis[e[i].x] == 0) continue;
addto({depth[lca(e[i].x, e[i].y)], dis[1][e[i].x]} ,alt[e[i].y]);
}
for(ll i = 0; i < m; ++i){
if(used[i] == 0){
ans[i] += min(dis[1][n], dis[1][e[i].y] + e[i].z + dis[e[i].x][n]);
continue;
}
ll cur = n;
ll d = inf;
while(cur){
if(cur == 1){
d = dis[1][n];
break;
}
if(cur == e[i].y){
for(auto u : inc[cur])
if(u.id != i){
d = min(d, dis[cur][n]+dis[1][u.x]+u.z);
}
break;
}
auto it = alt[cur].lower_bound({depth[e[i].y], 0});
if(it != alt[cur].begin()){
--it;
d = min(d, (*it).ss + dis[cur][n]);
}
cur = prt[cur][0];
}
//cout << i << ' ' << d << '\n';
ans[i] += d;
}
for(ll i = 1; i <= n; ++i){
depth[i] = vis[i] = 0;
for(ll j = 0; j < 10; ++j)
prt[i][j] = 0;
g[i].clear();
alt[i].clear();
}
for(ll i = 0; i < m; ++i) used[i] = 0;
createtree(n);
dfs(n, 0);
for(ll i = 0; i < m; ++i){
if(used[i] == 1) continue;
if(vis[e[i].x] == 0) continue;
addto({depth[lca(e[i].x, e[i].y)], dis[n][e[i].x]} ,alt[e[i].y]);
}
for(ll i = 0; i < m; ++i){
if(used[i] == 0){
ans[i] += min(dis[n][1], dis[n][e[i].y] + e[i].z + dis[e[i].x][1]);
continue;
}
ll cur = 1;
ll d = inf;
while(cur){
if(cur == n){
d = dis[n][1];
break;
}
if(cur == e[i].y){
for(auto u : inc[cur])
if(u.id != i){
d = min(d, dis[cur][1]+dis[n][u.x]+u.z);
}
break;
}
auto it = alt[cur].lower_bound({depth[e[i].y], 0});
if(it != alt[cur].begin()){
--it;
d = min(d, (*it).ss + dis[cur][1]);
}
cur = prt[cur][0];
}
ans[i] += d;
}
ll fin = dis[1][n]+dis[n][1];
for(ll i = 0; i < m; ++i){
fin = min(fin, ans[i]);
}
if(fin >= inf)
cout << -1;
else
cout << fin;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
896 KB |
Output is correct |
| 2 |
Correct |
13 ms |
768 KB |
Output is correct |
| 3 |
Correct |
15 ms |
872 KB |
Output is correct |
| 4 |
Correct |
15 ms |
896 KB |
Output is correct |
| 5 |
Incorrect |
5 ms |
512 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
6392 KB |
Output is correct |
| 2 |
Incorrect |
49 ms |
6648 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
896 KB |
Output is correct |
| 2 |
Correct |
13 ms |
768 KB |
Output is correct |
| 3 |
Correct |
39 ms |
4992 KB |
Output is correct |
| 4 |
Correct |
13 ms |
768 KB |
Output is correct |
| 5 |
Correct |
49 ms |
6392 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
49 ms |
6392 KB |
Output is correct |
| 9 |
Correct |
54 ms |
6268 KB |
Output is correct |
| 10 |
Incorrect |
49 ms |
6264 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
896 KB |
Output is correct |
| 2 |
Correct |
13 ms |
768 KB |
Output is correct |
| 3 |
Correct |
15 ms |
872 KB |
Output is correct |
| 4 |
Correct |
15 ms |
896 KB |
Output is correct |
| 5 |
Incorrect |
5 ms |
512 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
