Submission #701335

#	Time	Username	Problem	Language	Result	Execution time	Memory
701335		Jasonwei08	Robot (JOI21_ho_t4)	C++14	100 / 100	601 ms	85040 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define re(a, b, c, d) for (auto a = b; a <= c; a += d)
#define de(a, b, c, d) for (auto a = b; a >= c; a -= d)
#define ms (a); memset (a, 0, sizeof a);
#define imax INT_MAX
#define imin INT_MIN
#define wh(a) while (a --)
using namespace std;
using namespace std;
typedef long long lint;
typedef pair<int, int> pint;
typedef pair<lint, lint> plint;
const int MAX = 4e5 + 10;
int n, m, d[400005];
vector <int> a;
vector <pair <int, int> > g[400005];
vector <pair <int, pair <int, int> > > v[400005];
signed main () {
//	freopen ("10.in", "r", stdin);
	cin >> n >> m;
	re (i, 0, m - 1, 1) {
		int a, b, c, p;
		cin >> a >> b >> c >> p;
		v[a].push_back ({c, {p, b}});
		v[b].push_back ({c, {p, a}});
	}
	int sz = n;
	for (int i = 1; i < n; i++) {
		if (v[i].empty()) continue;
		sort (v[i].begin(), v[i].end());
		for (int l = 0, r = 0; l < v[i].size(); l = r) {
			lint s = 0;
			while (r < v[i].size() && v[i][l].first == v[i][r].first) s += v[i][r++].second.first;
			if (r - l == 1) g[i].emplace_back (0, v[i][l].second.second);
			else {
				g[i].emplace_back (0, ++sz);
				for (int j = l; j < r; j++) {
					pint x = v[i][j].second;
					g[i].emplace_back  (x);
					g[x.second].emplace_back (0, sz);
					g[sz].emplace_back (s - x.first, x.second);
				}
			}
		}
	}
	priority_queue<pair <int, int> > Q;
	Q.emplace (0, 1);
	for (int i = 1; i <= sz; i++) d[i] = 4e18;
	while (!Q.empty()) {
		auto t = Q.top();
		Q.pop();
		if (d[t.second] != 4e18) continue;
		d[t.second] = -t.first;
		for (auto nxt : g[t.second]) Q.emplace (t.first - nxt.first, nxt.second);
	}
	cout << (d[n] == 4e18 ? -1 : d[n]);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:32:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for (int l = 0, r = 0; l < v[i].size(); l = r) {
      |                          ~~^~~~~~~~~~~~~
Main.cpp:34:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |    while (r < v[i].size() && v[i][l].first == v[i][r].first) s += v[i][r++].second.first;
      |           ~~^~~~~~~~~~~~~

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