Submission #367950

#	Time	Username	Problem	Language	Result	Execution time	Memory
367950		rqi	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	75 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];

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


}

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];
			genDist(0, ed);
			pans+=dist[S[1]];
			genDist(1, ed);
			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]);
		ckmin(ans, pans);
	}

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

}

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