Submission #367952

#	Time	Username	Problem	Language	Result	Execution time	Memory
367952		rqi	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	368 ms	3948 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;

#define mp make_pair
#define sz(x) (int)(x).size()
#define f first
#define s second
#define pb push_back
#define all(x) begin(x), end(x)

void ckmin(ll& a, ll b){
	a = min(a, b);
}

const int mx = 50005;

const ll INF = 1e18;

int N, M;
int U[mx];
int V[mx];
int C[mx];
int D[mx];

vi adj[mx];

vi S = vi{0, 0};
vi spath[2]; //edge list of shortest path

int forbidden = -1; //forbidden edge
ll dist[mx];
ll o_dist[2][2][mx];

pi from[mx];
bool processed[mx];

void genDist(int typ, int disallowed = -1){
	forbidden = disallowed;

	for(int i = 1; i <= N; i++){
		dist[i] = INF;
	}


		
	// priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
	// dist[S[typ]] = 0;
	// pq.push(mp(dist[S[typ]], S[typ]));

	// while(sz(pq)){
	// 	int node = pq.top().s;
	// 	pq.pop();

	// 	for(auto u: adj[node]){
	// 		if(u == forbidden) continue;

	// 		int neigh = V[u];
	// 		ll cost = C[u];

	// 		if(dist[neigh] > dist[node]+cost){
	// 			dist[neigh] = dist[node]+cost;
	// 			from[neigh] = mp(node, u);
	// 			pq.push(mp(dist[neigh], neigh));
	// 		}
	// 	}
	// }

	for(int i = 1; i <= N; i++){
		processed[i] = 0;
	}

	dist[S[typ]] = 0;

	for(int iter = 1; iter <= N; iter++){
		ll min_dist = INF;
		int min_dist_node = 1;
		for(int i = 1; i <= N; i++){
			if(processed[i]) continue;
			if(dist[i] <= min_dist){
				min_dist = dist[i];
				min_dist_node = i;
			}
		}

		processed[min_dist_node] = 1;

		for(auto u: adj[min_dist_node]){
			if(u == forbidden) continue;
			int neigh = V[u];
			ll cost = C[u];

			if(dist[neigh] > dist[min_dist_node]+cost){
				dist[neigh] = dist[min_dist_node]+cost;
				from[neigh] = mp(min_dist_node, u);
			}
		}
	}

}

void reverseEdges(){
	for(int i = 1; i <= N; i++){
		adj[i].clear();
	}

	for(int i = 1; i <= M; i++){
		swap(U[i], V[i]);
	}

	for(int i = 1; i <= M; i++){
		adj[U[i]].pb(i);
	}
}

bool spec[mx];

int main(){
	cin >> N >> M;
	for(int i = 1; i <= M; i++){
		cin >> U[i] >> V[i] >> C[i] >> D[i];
		adj[U[i]].pb(i);
	}

	S[0] = 1;
	S[1] = N;

	ll ans = 0;

	for(int typ = 0; typ < 2; typ++){
		genDist(typ);
		ans+=dist[S[1-typ]]; //initialize to initial shortest paths

		// for(int i = 1; i <= N; i++){
		// 	cout << i << " " << dist[i] << "\n";
		// }

		// cout << dist[S[1-typ]] << "\n";

		if(dist[S[1-typ]] != INF){
			int curnode = S[1-typ];
			while(curnode != S[typ]){
				spath[typ].pb(from[curnode].s);
				curnode = from[curnode].f;
			}
			reverse(all(spath[typ]));
		}

		for(int i = 1; i <= N; i++){
			o_dist[typ][0][i] = dist[i];
		}
	}

	reverseEdges();

	for(int typ = 0; typ < 2; typ++){
		genDist(typ);

		for(int i = 1; i <= N; i++){
			o_dist[typ][1][i] = dist[i];
		}
	}

	reverseEdges();



	for(int typ = 0; typ < 2; typ++){
		for(auto ed: spath[typ]){
			spec[ed] = 1;
			ll pans = D[ed];

			U[M+1] = V[ed];
			V[M+1] = U[ed];
			C[M+1] = C[ed];

			adj[V[ed]].pb(M+1);

			genDist(0, ed);

			pans+=dist[S[1]];
			genDist(1, ed);
			adj[V[ed]].pop_back();
			pans+=dist[S[0]];
			ckmin(ans, pans);
		}
	}

	// for(int ed = 1; ed <= M; ed++){
	// 	spec[ed] = 1;
	// 	ll pans = D[ed];

	// 	U[M+1] = V[ed];
	// 	V[M+1] = U[ed];
	// 	C[M+1] = C[ed];

	// 	adj[V[ed]].pb(M+1);

	// 	genDist(0, ed);

	// 	pans+=dist[S[1]];
	// 	genDist(1, ed);
	// 	adj[V[ed]].pop_back();
	// 	pans+=dist[S[0]];
	// 	ckmin(ans, pans);
	// }

	for(int i = 1; i <= M; i++){
		if(spec[i]) continue;
		ll pans = D[i];
		pans+=min(o_dist[0][0][S[1]], o_dist[0][0][V[i]]+o_dist[1][1][U[i]]+C[i]);
		pans+=min(o_dist[1][0][S[0]], o_dist[1][0][V[i]]+o_dist[0][1][U[i]]+C[i]);

		// cout << i << " " << pans << "\n";
		// cout << o_dist[0][0][S[1]] << " " << o_dist[1][0][S[0]] << "\n";
		ckmin(ans, pans);
	}

	if(ans >= INF){
		cout << -1 << "\n";
	}
	else{
		cout << ans << "\n";
	}

}

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