Submission #1049125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049125		duckindog	Toll (BOI17_toll)	C++17	100 / 100	1051 ms	33232 KiB

toll

#include <bits/stdc++.h>

using namespace std;

const int N = 50'000 + 10,
					S = 400;
int k, n, m, q;
vector<pair<int, int>> ad[N];

void preSktra(int st, vector<int>& f) { 
	f = vector<int>(n + 1, 1'000'000'000);
  using pii = pair<int, int>;
  priority_queue<pii, vector<pii>, greater<>> q;
  q.push({f[st] = 0, st});
  while (q.size()) { 
    auto [d, u] = q.top(); q.pop();
    if (d != f[u]) continue;
    for (const auto& [v, w] : ad[u]) { 
      if (f[v] > d + w) q.push({f[v] = d + w, v});
    }
  }
}

int id[N], rvs[N], it;
vector<int> pF[S + 10];

int f[N];
int sktra(int st, int ed) { 
	int ret = 1'000'000'000;
	using pii = pair<int, int>;
  priority_queue<pii, vector<pii>, greater<>> q;
  q.push({f[st] = 0, st});
	vector<int> vt;
  while (q.size()) { 
		auto [d, u] = q.top(); q.pop();
		vt.push_back(u);
		if (d != f[u]) continue;
		if (id[u]) { 
			ret = min(ret, f[u] + pF[id[u]][ed]);
			continue;
		}
		for (const auto& [v, w] : ad[u]) { 
      if (f[v] > d + w) q.push({f[v] = d + w, v});
    }
	}
	ret = min(ret, f[ed]);
	for (const auto& i : vt) f[i] = 1'000'000'000;
	return ret >= 1'000'000'000 ? -1 : ret;
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> k >> n >> m >> q;
  for (int i = 1; i <= m; ++i) { 
    int u, v, w; cin >> u >> v >> w;
    ad[u].push_back({v, w});
  }

	for (int i = 0; i < n; ++i) { 
		if ((i / k) % S == 0) preSktra(i, pF[id[i] = ++it]);
	}

	memset(f, 63, sizeof f);
	while (q--) { 
		int a, b; cin >> a >> b;
		cout << sktra(a, b) << "\n";
	}
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44