Submission #516465

#	Time	Username	Problem	Language	Result	Execution time	Memory
516465		NachoLibre	Olympic Bus (JOI20_ho_t4)	C++17	37 / 100	1082 ms	3216 KiB

ho_t4

#include <bits/stdc++.h>
#pragma GCC optimize("-O3")
#pragma GCC optimize("-Ofast")
#pragma GCC optimize("unroll-loops")
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;

const int inf = 2e9;

vector<ll> D(int x, vector<vector<array<int, 3> > > &v, vector<bool> &u, int ub = 0, int bl = 0) {
	int n = sz(v) - 1;
	vector<ll> d(n + 1, -1);
	vector<int> prv(n + 1);
	vector<int> pre(n + 1);
	d[x] = 0;
	set<array<int, 2> > s;
	s.insert({0, x});
	while(sz(s)) {
		int y = (*s.begin())[1];
		s.erase(s.begin());
		for(array<int, 3> z : v[y]) {
			if(z[2] == bl) continue;
			if(d[z[0]] == -1 || d[z[0]] > d[y] + z[1]) {
				if(d[z[0]] != -1) { s.erase(s.find({(int)d[z[0]], z[0]})); }
				d[z[0]] = d[y] + z[1];
				prv[z[0]] = y;
				pre[z[0]] = z[2];
				s.insert({(int)d[z[0]], z[0]});
			}
		}
	}
	if(ub) {
		while(prv[ub]) {
			u[pre[ub]] = 1;
			ub = prv[ub];
		}
	}
	for(ll &x : d) {
		if(x == -1) x = inf;
	}
	return d;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	#ifdef x
	freopen("x.txt", "r", stdin);
	#endif
	int n, m;
	cin >> n >> m;
	vector<vector<array<int, 3> > > v(n + 1);
	vector<vector<array<int, 3> > > u(n + 1);
	array<int, 4> x[m + 1];
	for(int i = 1; i <= m; ++i) {
		for(int j = 0; j < 4; ++j) {
			cin >> x[i][j];
		}
		v[x[i][0]].push_back({x[i][1], x[i][2], i});
		u[x[i][1]].push_back({x[i][0], x[i][2], i});
	}
	vector<bool> rlt(m + 1);
	vector<ll> fro = D(1, v, rlt, n);
	vector<ll> frn = D(n, v, rlt, 1);
	vector<ll> too = D(1, u, rlt);
	vector<ll> ton = D(n, u, rlt);
	ll fp = fro[n] + frn[1];
	for(int i = 1; i <= m; ++i) {
		ll tp = 0;
		if(rlt[i]) {
			v[x[i][1]].push_back({x[i][0], x[i][2], x[i][3]});
			tp = x[i][3] + D(1, v, rlt, 0, i)[n] + D(n, v, rlt, 0, i)[1];
			v[x[i][1]].pop_back();
		} else {
			tp = x[i][3]
			+ min(fro[n], fro[x[i][1]] + x[i][2] + ton[x[i][0]])
			+ min(frn[1], frn[x[i][1]] + x[i][2] + too[x[i][0]]);
		}
		fp = min(fp, tp);
	}
	if(fp >= inf) fp = -1;
	cout << fp << endl;
	return 0;
}

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