Submission #543681

#	Time	Username	Problem	Language	Result	Execution time	Memory
543681		Asymmetry	Robot (JOI21_ho_t4)	C++17	0 / 100	361 ms	38108 KiB

Main

//Autor: Bartłomiej Czarkowski
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif

const int N = 101000;
int n, m, a, b, c, p;
map<int, vector<pair<int, int>>> mp[N];
long long odl[N];
priority_queue<pair<long long, int>> pq;

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d%d%d", &a, &b, &c, &p);
		mp[a][c].push_back({b, p});
		mp[b][c].push_back({a, p});
	}
	for (int i = 2; i <= n; ++i) {
		odl[i] = 1e18;
	}
	pq.push({0, 1});
	while (!pq.empty()) {
		long long w = -pq.top().first;
		int x = pq.top().second;
		pq.pop();
		//~ debug(w, x);
		if (x == n) {
			printf("%lld\n", odl[x]);
			return 0;
		}
		if (odl[x] != w) {
			continue;
		}
		for (auto i : mp[x]) {
			long long sum = 0;
			for (auto j : i.second) {
				sum += j.second;
			}
			for (auto [a, b] : i.second) {
				if (odl[a] > w + min(sum - b, (long long)b)) {
					odl[a] = w + min(sum - b, (long long)b);
					pq.push({-odl[a], a});
				}
			}
		}
	}
	printf("-1\n");
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |   scanf("%d%d%d%d", &a, &b, &c, &p);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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