Submission #959936

#	Time	Username	Problem	Language	Result	Execution time	Memory
959936		happy_node	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	98 ms	9644 KiB

ho_t4

#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';
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63