Submission #1253724

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253724		mingga	Robot (JOI21_ho_t4)	C++20	100 / 100	96 ms	21488 KiB

Main

// Author: caption_mingle
#include "bits/stdc++.h"

using namespace std;

#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define int long long
const int mod = 1e9 + 7;
const int inf = 2e18;
const int N = 1e5 + 7;
int n, m;
struct edge {
	int v, c, p;
};
int f[N], mn[N * 2], cnt[N * 2];
vector<edge> g[N];

signed main() {
	cin.tie(0) -> sync_with_stdio(0);
	#define task ""
	if(fopen(task ".INP", "r")) {
		freopen(task ".INP", "r", stdin);
		freopen(task ".OUT", "w", stdout);
	}
	cin >> n >> m;
	for(int i = 1; i <= m; i++) {
		int u, v, c, p; cin >> u >> v >> c >> p;
		g[u].pb({v, c, p});
		g[v].pb({u, c, p});
	}
	priority_queue<pair<int, int>> q;
	for(int i = 1; i <= n; i++) f[i] = inf;
	f[1] = 0;
	q.push({0, 1});
	while(sz(q)) {
		auto [W, u] = q.top(); q.pop();
		W = -W;
		if(W != f[u]) continue;
		for(auto [v, c, p] : g[u]) {
			mn[c] = inf;
			cnt[c] = 0;
		}
		for(auto [v, c, p] : g[u]) {
			cnt[c] += p;
		}
		for(auto [v, c, p] : g[u]) {
 			mn[c] = min(mn[c], f[v] + cnt[c]);
		}
		for(auto [v, c, p] : g[u]) {
			int cost = min({W + p, W + cnt[c] - p, mn[c] - p});
			if(f[v] > cost) {
				f[v] = cost;
				q.push({-f[v], v});
			}
		}
	}
	if(f[n] == inf) f[n] = -1;
	cout << f[n] << ln;
    cerr << "\nTime: " << clock() * 1000 / CLOCKS_PER_SEC;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:27:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |                 freopen(task ".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:28:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |                 freopen(task ".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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