oj.uz

Submission #959880

# Submission time Handle Problem Language Result Execution time Memory
959880 2024-04-09T09:18:24 Z happy_node Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 1 ms 860 KB 
#include <bits/stdc++.h>
using namespace std;

/*
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;
int 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<MX;i++) 
		for(int j=0;j<MX;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);

	int 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]);
		// N -> 1 : pake yg diflip
		ans=min(ans,D[i]+dist[1][N]+dist[N][V[i]]+dist[U[i]][1]+C[i]);
	}

	cout<<ans<<'\n';
}

Compilation message

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:87:14: warning: iteration 205 invokes undefined behavior [-Waggressive-loop-optimizations]
   87 |    dist[i][j]=2e9;
      |    ~~~~~~~~~~^~~~
ho_t4.cpp:86:16: note: within this loop
   86 |   for(int j=0;j<MX;j++)
      |               ~^~~
ho_t4.cpp:87:14: warning: iteration 205 invokes undefined behavior [-Waggressive-loop-optimizations]
   87 |    dist[i][j]=2e9;
      |    ~~~~~~~~~~^~~~
ho_t4.cpp:85:15: note: within this loop
   85 |  for(int i=0;i<MX;i++)
      |              ~^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 856 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -