Submission #726183

#	Time	Username	Problem	Language	Result	Execution time	Memory
726183		GusterGoose27	Wild Boar (JOI18_wild_boar)	C++17	12 / 100	691 ms	862276 KiB

wild_boar

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, bool> plb;
typedef pair<ll, int> pli;

const int MAXN = 100;
const int MAX_PATH = 1e5;
const ll inf = 1e15;
int n, m, t, l;

class path {
public:
	ll len;
	int s, e;
	path(ll l, int s, int e) : len(l), s(s), e(e) {}
	path() {}
};

int hsh(int i, int j) {
	return n*i+j; // j is prev node, i is cur node
}

vector<pii> edges[MAXN];
vector<pii> edges2[MAXN*MAXN];
ll dist[MAXN*MAXN][MAXN*MAXN];
int seq[MAX_PATH];

void dijkstra(int s) {
	priority_queue<pli, vector<pli>, greater<pli>> pq;
	fill(dist[s], dist[s]+n*n, inf);
	dist[s][s] = 0;
	pq.push(pli(0, s));
	while (!pq.empty()) {
		pii tp = pq.top();
		pq.pop();
		if (dist[s][tp.second] < tp.first) continue;
		for (pii e: edges2[tp.second]) {
			ll ndist = tp.first+e.second;
			if (ndist < dist[s][e.first]) {
				dist[s][e.first] = ndist;
				pq.push(pli(ndist, e.first));
			}
		}
	}
}

ll dp[MAX_PATH][MAXN];

ll make_dp() {
	fill(dp[l-1], dp[l-1]+n, 0);
	for (int i = l-2; i > 0; i--) {
		for (pii j: edges[seq[i]]) {
			dp[i][j.first] = inf;
			for (pii k: edges[seq[i+1]]) {
				dp[i][j.first] = min(dp[i][j.first], dp[i+1][k.first]+dist[hsh(seq[i],j.first)][hsh(seq[i+1], k.first)]);
			}
		}
	}
	ll ans = inf;
	for (pii i: edges[seq[0]]) 
		for (pii j: edges[seq[1]]) ans = min(ans, dp[1][j.first]+i.second+dist[hsh(i.first, seq[0])][hsh(seq[1], j.first)]);
	if (ans == inf) return -1;
	return ans;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m >> t >> l;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c; a--; b--;
		edges[a].push_back(pii(b, c));
		edges[b].push_back(pii(a, c));
	}
	for (int i = 0; i < n; i++) {
		for (pii j: edges[i]) {
			for (pii k: edges[i]) {
				if (k.first == j.first) continue;
				edges2[hsh(i, j.first)].push_back(pii(hsh(k.first, i), k.second));
			}
		}
	}
	for (int i = 0; i < n*n; i++) {
		dijkstra(i);
	}
	for (int i = 0; i < l; i++) {
		cin >> seq[i]; seq[i]--;
	}
	for (int i = 0; i < t; i++) {
		int p, v; cin >> p >> v;
		p--; v--;
		seq[p] = v;
		cout << make_dp() << "\n";
	}
}

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