Submission #1176210

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176210		Tsagana	Robot (JOI21_ho_t4)	C++20	0 / 100	39 ms	10172 KiB

Main

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

vector<array<int, 3>> adj[100010];
int S[200010];
int dp[100010];
int mn[200010];
int vis[200010];

void solve () {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v, c, p;
		cin >> u >> v >> c >> p;
		adj[u].pb({v, p, c});
		adj[v].pb({u, p, c});
	}
	pq<pair<int, int>> q;
	fill(dp, dp + n + 1, 1e18);
	dp[1] = 0;
	q.push({0, 1});
	while (!q.empty()) {
		auto [D, s] = q.top(); q.pop();
		if (vis[s]) continue;
		vis[s] = 1;
		for (auto [u, p, c] : adj[s]) mn[c] = 1e18, S[c] = 0;
		for (auto [u, p, c] : adj[s]) S[c] += p;
		for (auto [u, p, c] : adj[s]) mn[c] = min(mn[c], dp[u] + S[c]);
		for (auto [u, p, c] : adj[s]) {
			if (dp[u] > min({dp[s] + p, dp[s] + S[c] - p, mn[c] - p})) {
				dp[u] = min({dp[s] + p, dp[s] + S[c] - p, mn[c] - p});
				q.push({dp[u], u});
			}
		}
	}
	cout << (dp[n] > 1e15 ? -1 : dp[n]) << '\n';
}
signed main() {IOS solve(); return 0;}

• Subtask 1: 0 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42