Submission #202750

#	Time	Username	Problem	Language	Result	Execution time	Memory
202750		klimoza	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	204 ms	4984 KiB

ho_t4

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <math.h>
#include <cmath>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
#include <random>
#include <deque>
#include <bitset>
#include <string>
#include <queue>
#include <complex>

//#define int long long

#define mp(a, b) make_pair(a, b)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

#define endl '\n'

using namespace std;
typedef long long ll;
typedef long double ld;

mt19937 mrand(random_device{}());

double PI = acos((double)-1);
const double eps = 1e-8;
const ll inf0 = 1023 * 1024 * 1024;
const ll inf = inf0 * inf0;
//const ll mod = 1e9 + 7;
//const ll mod = 777777773;
const ll mod = 1e9 + 7;
const ll MOD = mod * mod;

void solve();
void scan();

signed main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cout << fixed; cout.precision(15);
	solve();
}

struct Edge {
	int u, v;
	ll c, d;
	int i;
	Edge() {}
	Edge(int i, int u, int v, ll c, ll d) : u(u), v(v), c(c), d(d), i(i){}
};	

const int N = 201;

vector<Edge> g[N];

ll d1[N], d2[N];

bool used[N];

void djikstra(int s, ll* d) {
	for (int i = 0; i < N; i++)
		d[i] = inf;
	d[s] = 0;
	fill(used, used + N, false);
	for (int i = 0; i < N; i++) {
		int v = -1;
		for (int j = 0; j < N; j++) {
			if (!used[j] && (v == -1 || d[j] < d[v]))
				v = j;
		}
		used[v] = true;
		if (d[v] == inf) break;
		for (auto e : g[v]) {
			if (d[e.v] > d[v] + e.c) {
				d[e.v] = d[v] + e.c;
			}
		}
	}
}

ll jopa[N][N];

void solve() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i == j) jopa[i][j] = 0;
			else jopa[i][j] = inf;
		}
	}
	vector<Edge> ed(m);
	for (int i = 0; i < m; i++) {
		cin >> ed[i].u >> ed[i].v >> ed[i].c >> ed[i].d;
		ed[i].u--; ed[i].v--;
		jopa[ed[i].u][ed[i].v] = min(jopa[ed[i].u][ed[i].v], ed[i].c);
		ed[i].i = i;
		g[ed[i].u].push_back(ed[i]);
	}
	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (jopa[i][k] != inf && jopa[k][j] != inf && jopa[i][j] > jopa[i][k] + jopa[k][j])
					jopa[i][j] = jopa[i][k] + jopa[k][j];
			}
		}
	}
	vector<ll> ds1(n, inf), ds2(n, inf);
	vector<Edge> p1(n), p2(n);
	ds1[0] = 0; ds2[n - 1] = 0;
	set<pair<ll, int>> f;
	for (int i = 0; i < n; i++)
		f.insert({ ds1[i], i });
	while (!f.empty()) {
		auto v = *f.begin();
		if (v.first == inf) break;
		f.erase(f.begin());
		for (auto e : g[v.second]) {
			if (ds1[e.v] > v.first + e.c) {
				f.erase({ ds1[e.v], e.v });
				p1[e.v] = e;
				ds1[e.v] = v.first + e.c;
				f.insert({ ds1[e.v], e.v });
			}
		}
	}
	f.clear();
	for (int i = 0; i < n; i++)
		f.insert({ ds2[i], i });
	while (!f.empty()) {
		auto v = *f.begin();
		if (v.first == inf) break;
		f.erase(f.begin());
		for (auto e : g[v.second]) {
			if (ds2[e.v] > v.first + e.c) {
				f.erase({ ds2[e.v], e.v });
				p2[e.v] = e;
				ds2[e.v] = v.first + e.c;
				f.insert({ ds2[e.v], e.v });
			}
		}
	}
	ll ans = inf;
	if (ds1[n - 1] != inf && ds2[0] != inf)
		ans = ds1[n - 1] + ds2[0];
	vector<int> tmp;
	for (int i = 1; i < n; i++)
		if(ds1[i] != inf)
			tmp.push_back(p1[i].i);
	for (int i = 0; i < (n - 1); i++)
		if(ds2[i] != inf)
			tmp.push_back(p2[i].i);
	sort(all(tmp));
	tmp.erase(unique(all(tmp)), tmp.end());
	vector<bool> cool(m);
	for (int j : tmp) {
		cool[j] = true;
		int h = -1;
		//cout << ed[j].i << endl;
		for (int k = 0; k < g[ed[j].u].size(); k++) {
			if (g[ed[j].u][k].i == ed[j].i) {
				h = k;
				break;
			}
		}
		g[ed[j].u].erase(g[ed[j].u].begin() + h);
		g[ed[j].v].push_back(Edge(ed[j].i, ed[j].v, ed[j].u, ed[j].c, ed[j].d));
		djikstra(0, d1);
		djikstra(n - 1, d2);
		if (d1[n - 1] != inf && d2[0] != inf)
			ans = min(ans, d1[n - 1] + d2[0] + ed[j].d);
		g[ed[j].u].push_back(ed[j]);
		g[ed[j].v].pop_back();
	}
	for (int i = 0; i < m; i++) {
		if (cool[i]) continue;
		ll f1 = jopa[0][n - 1];
		if (jopa[0][ed[i].v] != inf && jopa[ed[i].u][n - 1] != inf) 
			f1 = min(f1, jopa[0][ed[i].v] + ed[i].c + jopa[ed[i].u][n - 1]);
		ll f2 = jopa[n - 1][0];
		if (jopa[n - 1][ed[i].v] != inf && jopa[ed[i].u][0] != inf)
			f2 = min(f2, jopa[n - 1][ed[i].v] + ed[i].c + jopa[ed[i].u][0]);
		ans = min(ans, f1 + f2 + ed[i].d);
	}
	if (ans == inf) cout << -1 << endl;
	else cout << ans << endl;
	return;
}

Compilation message (stderr)

ho_t4.cpp: In function 'void solve()':
ho_t4.cpp:173:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int k = 0; k < g[ed[j].u].size(); k++) {
                   ~~^~~~~~~~~~~~~~~~~~~

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