oj.uz

Submission #959890

# Submission time Handle Problem Language Result Execution time Memory
959890 2024-04-09T09:25:48 Z happy_node Olympic Bus (JOI20_ho_t4) C++17
11 / 100
 42 ms 4188 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});
			}
		}
	}
}

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];
	}

	for(int i=0;i<M;i++) {
		// 1 -> N : pake yg diflip
		ans=min(ans,D[i]+dist[1][V[i]]+dist[U[i]][N]+C[i]+dist[N][1]);
		ans=min(ans,D[i]+dist[1][N]+dist[N][V[i]]+dist[U[i]][1]+C[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 3 ms 856 KB Output is correct
2 Correct 1 ms 756 KB Output is correct
3 Correct 5 ms 860 KB Output is correct
4 Correct 5 ms 856 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Incorrect 0 ms 604 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 35 ms 2904 KB Output is correct
2 Correct 36 ms 2908 KB Output is correct
3 Correct 42 ms 2908 KB Output is correct
4 Correct 6 ms 856 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 29 ms 3048 KB Output is correct
10 Correct 30 ms 4188 KB Output is correct
11 Correct 31 ms 4184 KB Output is correct
12 Correct 36 ms 4188 KB Output is correct
13 Correct 30 ms 4036 KB Output is correct
14 Correct 31 ms 4184 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 19 ms 2392 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 23 ms 3020 KB Output is correct
6 Incorrect 1 ms 600 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

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