Submission #524446

#	Time	Username	Problem	Language	Result	Execution time	Memory
524446		Sohsoh84	Wild Boar (JOI18_wild_boar)	C++17	62 / 100	8553 ms	285976 KiB

wild_boar

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 2e3 + 10; // 1e5 ?
const ll MAXL = 1e5 + 10;
const ll INF = 4e18;

vector<int> adj[MAXN];
int from[MAXN], to[MAXN], n, m, t, l, sup_list[MAXL];
ll dist[MAXN][3][MAXN][3], w[MAXN], ans[2][MAXN << 2];

inline int f(int ind, int v) {
	return from[ind] + to[ind] - v;
}

inline int edge_side(int ind, int v) {
	return from[ind] == v ? 0 : 1;
}

inline void dijkstra(int tv, int tstate) {
	dist[tv][tstate][tv][tstate] = 0;
	priority_queue<plll, vector<plll>, greater<plll>> pq;
	pq.push({0, {tv, tstate}});

	while (!pq.empty()) {
		int fv = pq.top().Y.X, fstate = pq.top().Y.Y;
		ll d_v = pq.top().X;
		pq.pop();
		if (d_v != dist[tv][tstate][fv][fstate]) continue; 
	
		int lst = fv, v = 0;
		if (fstate == 0) v = from[lst];
		else if (fstate == 1) v = to[lst];
		else v = lst, lst = -1;

		for (int ind : adj[v]) {
			if (ind == lst) continue;
			int u = f(ind, v), state = edge_side(ind, u);
			ll d_u = d_v + w[ind];

			if (d_u < dist[tv][tstate][ind][state]) {
				dist[tv][tstate][ind][state] = d_u;
				pq.push({d_u, {ind, state}});
			}
		}
	}
}

inline vector<pll> v_states(int v) {
	vector<pll> ans;
	for (int ind : adj[v])
		ans.push_back({ind, edge_side(ind, v)});
	return ans;
}

inline void majik(pair<plll, plll>& a, plll b) {
	if (b.X < a.X.X) {
		a.Y = a.X;
		a.X = b;
	} else if (b.X < a.Y.X) a.Y = b;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m >> t >> l;
	for (int i = 1; i <= m; i++) {
		cin >> from[i] >> to[i] >> w[i];
		adj[from[i]].push_back(i);
		adj[to[i]].push_back(i);
	}

	for (int i = 0; i < MAXN; i++)
		for (int j = 0; j < 3; j++)
			for (int a = 0; a < MAXN; a++)
				for (int b = 0; b < 3; b++)
					dist[i][j][a][b] = INF;

	for (int v = 1; v <= n; v++)
			dijkstra(v, 2);
	for (int i = 1; i <= m; i++)
		dijkstra(i, 1), dijkstra(i, 0);

	for (int i = 1; i <= l; i++) cin >> sup_list[i];
	while (t--) {
		int p, c;
		cin >> p >> c;
		sup_list[p] = c;
	}

	ans[1][0] = 0; // !!!
	ll fans = INF;
	
	for (int i = 2; i <= l; i++) {
		vector<pll> B = v_states(sup_list[i]);
		pair<plll, plll> A = {{INF, {INF, INF}}, {INF, {INF, INF}}};
	
		int ind = i & 1;
		if (i == 2) A.X = {0, {sup_list[i - 1], 2}};
		else {
			vector<pll> tmp = v_states(sup_list[i - 1]);
			for (int i = 0; i < int(tmp.size()); i++)
				majik(A, {ans[ind ^ 1][i], tmp[i]});
		}

		fill(ans[ind], ans[ind] + int(B.size()), INF);

		fans = INF;
		for (int i = 0; i < int(B.size()); i++) {
			if (A.X.X < INF) ans[ind][i] = min(ans[ind][i], A.X.X + dist[A.X.Y.X][A.X.Y.Y][B[i].X][B[i].Y]);
			if (A.Y.X < INF) ans[ind][i] = min(ans[ind][i], A.Y.X + dist[A.Y.Y.X][A.Y.Y.Y][B[i].X][B[i].Y]);
			fans = min(fans, ans[ind][i]);
		}
/*
		if (i == 3) {
			for (pll e : B)
				cerr << e.X << sep << e.Y << endl;
			debug(ans[ind][1])
		}
*/	}

	cout << (fans == INF ? -1 : fans) << endl;
	return 0;	
}

• Subtask 1: 12 / 12
• Subtask 2: 35 / 35
• Subtask 3: 15 / 15
• Subtask 4: 0 / 38