oj.uz

Submission #959888

# Submission time Handle Problem Language Result Execution time Memory
959888 2024-04-09T09:24:12 Z happy_node Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 37 ms 4088 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]);
	}

	cout<<(ans==2e9?-1:ans)<<'\n';
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2904 KB Output is correct
2 Correct 36 ms 2904 KB Output is correct
3 Correct 37 ms 2904 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 1 ms 604 KB Output is correct
9 Incorrect 29 ms 4088 KB Output isn't correct
10 Halted 0 ms 0 KB -

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 3108 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 23 ms 3932 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 4 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 5 ms 860 KB Output is correct
4 Correct 6 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Incorrect 1 ms 604 KB Output isn't correct
8 Halted 0 ms 0 KB -