#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/*
DIST(X,Y, [baru / ga baru])
N M log M
buat dist x ke y tapi ga boleh langsung
EDGE(X) -> edge terpendek dari Ux->Vx yang bukan dirinya sendiri
Iterate semua edge, coba kalo dia yang diinvert
Ada 3 kasus
Let edge yg baru diinvert ke u->v
1. Pake edge yg diinvert buat pulang pergi
dist(1, u) + dist(v, N) + dist(N, u) + dist(v, 1)
2. Pake edge yg diinvert buat pulang doang
f(x) + dist(N,u) + dist(v, 1)
f(x) = jarak terpendek dari 1 -> N tanpa menggunakan edge x
f(x)
1. ga lewat u dan v
2. ga lewat u
3. ga lewat v
4. lewat u dan v
kasus 1. dan 2. di handle sudah dengan ngeblock node v
kasus 3. di handle dengan block node u
kasus 4. artinya lewat u dan v namun ga lewat edge x
4.1 lewat u dulu baru v
*) syarat ini -> dist(1,u) <= dist(1, v)
4.1.1 dari u -> v tapi ga pake edge (u,v) sama sekali
f(x) = dist(1,u) + DIST(u,v,ga baru) + dist(v, N)
4.1.2 dari u -> v dan sempat pake edge (u,v) yang bukan edge x
f(x) = dist(1,u) + EDGE(x) + dist(v, N)
4.2 lewat v dulu baru u
*) syarat ini dist(1,v) <= dist(1, u)
REV(x) = minimum dari semua edge v->u
dist(1, v) + REV(x) + dist(u, N)
3. Pake edge yg diinvert buat pergi doang
Subtask 2 itu bisa iterate semua edge terus langsung di minimum aja karena
connectivity nya ngga berkurang, cuman bisa nambah....
*/
const int MX=5e4+5;
int N,M;
ll dist[205][205], U[MX], V[MX], C[MX], D[MX];
vector<array<int,2>> adj[205];
void work(int src) {
priority_queue<pair<int,int>> pq;
pq.push({0,src});
dist[src][src]=0;
while(!pq.empty()) {
auto [d,v]=pq.top(); pq.pop();
d=-d;
if(d>dist[src][v]) continue;
for(auto [u,w]:adj[v]) {
if(dist[src][u]>dist[src][v]+w) {
dist[src][u]=dist[src][v]+w;
pq.push({-dist[src][u],u});
}
}
}
}
ll f[205][205]; // f(x,y) = jarak dari 1 -> y kalo x diblock
ll g[205][205]; // g(x,y) = jarak dari N -> y kalo x diblock
ll edge[MX]; // alternatif dari suatu edge kalo itu dibalik arahnya
ll h[205][205]; // h(x,y,status) = jarak dari x ke y dan status = min(1, # edge dipakai - 1)
void F(int b) {
priority_queue<pair<int,int>> pq;
if(b==1) return;
pq.push({0,1});
f[b][1]=0;
while(!pq.empty()) {
auto [d,v]=pq.top(); pq.pop();
d=-d;
if(d>f[b][v]) continue;
for(auto [u,w]:adj[v]) {
if(f[b][u]>f[b][v]+w && u!=b) {
f[b][u]=f[b][v]+w;
pq.push({-f[b][u],u});
}
}
}
}
void G(int b) {
priority_queue<pair<int,int>> pq;
if(b==N) return;
pq.push({0,N});
g[b][N]=0;
while(!pq.empty()) {
auto [d,v]=pq.top(); pq.pop();
d=-d;
if(d>g[b][v]) continue;
for(auto [u,w]:adj[v]) {
if(g[b][u]>g[b][v]+w && u!=b) {
g[b][u]=g[b][v]+w;
pq.push({-g[b][u],u});
}
}
}
}
multiset<int> E[205][205];
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
for(int i=0;i<205;i++)
for(int j=0;j<205;j++) {
dist[i][j]=2e9;
f[i][j]=2e9;
g[i][j]=2e9;
h[i][j]=2e9;
}
cin>>N>>M;
for(int i=0;i<M;i++) {
int u,v,c,d;
cin>>u>>v>>c>>d;
U[i]=u;
V[i]=v;
c=1;
C[i]=c;
D[i]=d;
adj[u].push_back({v,c});
E[u][v].insert(c);
}
for(int i=1;i<=N;i++) {
work(i);
F(i);
G(i);
}
for(int i=0;i<M;i++) {
int u=U[i],v=V[i];
E[u][v].erase(E[u][v].find(C[i]));
if(E[u][v].size()) edge[i]=*E[u][v].begin();
else edge[i]=2e9;
E[u][v].insert(C[i]);
}
ll ans=2e9;
if(dist[1][N]!=2e9 && dist[N][1]!=2e9) {
ans=dist[1][N]+dist[N][1];
}
/*
bedanya subtask - 2 dengan full adalah baliknya gabisa tinggal dist(N,1) gitu karena udah beda
bikin dist kalo kita block u, block v, dan paksa dia balik lewat (u,v) tapi tanyain ada cara lain ga tanpa pake edge ini
harus dicek juga kalo dist(1,v)<=dist(1,u) karena nnti bisa aja pake edge yg lama dulu
*/
for(int i=1;i<=N;i++) {
for(int j=1;j<=N;j++) {
for(int k=1;k<=N;k++) {
if(i==j||i==k||j==k) continue;
// i -> k, k -> j
if(dist[i][k]<dist[i][j]&&E[k][j].size()) {
h[i][j]=min(h[i][j],h[i][k]+(*E[k][j].begin()));
}
}
}
}
for(int i=0;i<M;i++) {
if(dist[1][V[i]]<dist[1][U[i]]&&dist[U[i]][N]!=2e9) {
// 1->N pake inverted edge
// ll w=min(g[U[i]][1], g[V[i]][1]);
// w=min(w,dist[N][U[i]]+dist[V[i]][1]+h[U[i]][V[i]]);
// w=min(w,dist[N][V[i]]+dist[U[i]][1]+h[V[i]][U[i]]);
// cout<<"1: "<<D[i]+dist[1][V[i]]+dist[U[i]][N]+C[i]+w<<'\n';
// ans=min(ans,D[i]+dist[1][V[i]]+dist[U[i]][N]+C[i]+w);
bool can=0;
if(g[U[i]][1]!=2e9) can=1;
if(g[V[i]][1]!=2e9) can=1;
if(dist[N][V[i]]<dist[N][U[i]]&&dist[U[i]][1]!=2e9) can=1;
if(dist[N][U[i]]<dist[N][V[i]]&&dist[V[i]][1]!=2e9&&h[U[i]][V[i]]!=2e9) can=1;
if(dist[N][U[i]]<dist[N][V[i]]&&dist[V[i]][1]!=2e9&&edge[i]!=2e9) can=1;
if(can) ans=min(ans,D[i]);
}
if(dist[N][V[i]]<dist[N][U[i]]&&dist[U[i]][1]!=2e9) {
// N->1 pake inverted edge
// ll w=min(f[U[i]][N],f[V[i]][N]);
// w=min(w,dist[1][U[i]]+dist[V[i]][N]+h[U[i]][V[i]]);
// w=min(w,dist[1][V[i]]+dist[U[i]][N]+h[V[i]][U[i]]);
// cout<<"2: "<<D[i]+w+dist[N][V[i]]+dist[U[i]][1]+C[i]<<'\n';
// ans=min(ans,D[i]+w+dist[N][V[i]]+dist[U[i]][1]+C[i]);
// cout<<"2: "<<D[i]<<" "<<i<<'\n';
bool can=0;
if(f[U[i]][N]!=2e9) can=1;
if(f[V[i]][N]!=2e9) can=1;
if(dist[1][V[i]]<dist[1][U[i]]&&dist[U[i]][N]!=2e9) can=1;
if(dist[1][U[i]]<dist[1][V[i]]&&dist[V[i]][N]!=2e9&&h[U[i]][V[i]]!=2e9) can=1;
if(dist[1][U[i]]<dist[1][V[i]]&&dist[V[i]][N]!=2e9&&edge[i]!=2e9) can=1;
if(can) ans=min(ans,D[i]);
ans=min(ans,D[i]);
}
if(dist[1][V[i]]<dist[1][U[i]]&&dist[U[i]][N]!=2e9
&&dist[N][V[i]]<dist[N][U[i]]&&dist[U[i]][1]!=2e9) {
// bolak balik pake inverted edge
// cout<<"3: "<<D[i]+dist[1][V[i]]+dist[U[i]][N]+C[i]+dist[N][V[i]]+dist[U[i]][1]+C[i]<<'\n';
// ans=min(ans,D[i]+dist[1][V[i]]+dist[U[i]][N]+C[i]+dist[N][V[i]]+dist[U[i]][1]+C[i]);
// cout<<"3: "<<D[i]<<" "<<i<<'\n';
ans=min(ans,D[i]);
}
}
cout<<(ans==2e9?-1:ans)<<'\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
4952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
98 ms |
9644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
4956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
4952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
