oj.uz

Submission #959891

# Submission time Handle Problem Language Result Execution time Memory
959891 2024-04-09T09:30:52 Z happy_node Olympic Bus (JOI20_ho_t4) C++17
11 / 100
 38 ms 3520 KB 
#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 d[205][205][2];



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;

	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[i]=c;
		D[i]=d;
		adj[u].push_back({v,c});
	}

	for(int i=1;i<=N;i++) 
		work(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=0;i<M;i++) {
		if(dist[1][V[i]]<=dist[1][U[i]])
			ans=min(ans,D[i]+dist[1][V[i]]+dist[U[i]][N]+C[i]+dist[N][1]);
		if(dist[N][V[i]]<=dist[N][U[i]])
			ans=min(ans,D[i]+dist[1][N]+dist[N][V[i]]+dist[U[i]][1]+C[i]);
		if(dist[1][V[i]]<=dist[1][U[i]]&&dist[N][V[i]]<=dist[N][U[i]])
			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<<(ans==2e9?-1:ans)<<'\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2648 KB Output is correct
2 Correct 2 ms 2904 KB Output is correct
3 Correct 5 ms 2652 KB Output is correct
4 Correct 6 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Incorrect 1 ms 2652 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3520 KB Output is correct
2 Correct 36 ms 3420 KB Output is correct
3 Correct 38 ms 3420 KB Output is correct
4 Correct 6 ms 2652 KB Output is correct
5 Correct 4 ms 2648 KB Output is correct
6 Correct 2 ms 2648 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 28 ms 3444 KB Output is correct
10 Correct 29 ms 3420 KB Output is correct
11 Correct 31 ms 3416 KB Output is correct
12 Correct 31 ms 3420 KB Output is correct
13 Correct 30 ms 3420 KB Output is correct
14 Correct 30 ms 3420 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 21 ms 3164 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 25 ms 3496 KB Output is correct
6 Incorrect 1 ms 2652 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2648 KB Output is correct
2 Correct 2 ms 2904 KB Output is correct
3 Correct 5 ms 2652 KB Output is correct
4 Correct 6 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Incorrect 1 ms 2652 KB Output isn't correct
8 Halted 0 ms 0 KB -