Submission #1040136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040136		sssamui	Robot (JOI21_ho_t4)	C++17	100 / 100	751 ms	93448 KiB

Main

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
using namespace std;
using ll = long long;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	cin >> n >> m;
	vector<map<int, pair<vector<pair<ll, int>>, ll>>> adj(n + 1);
	vector<map<int, ll>> sm(n + 1);
	while (m--)
	{
		int a, b, c;
		ll p;
		cin >> a >> b >> c >> p;
		adj[a][c].first.push_back({ p, b }), adj[b][c].first.push_back({ p, a });
		adj[a][c].second += p, adj[b][c].second += p;
	}

	vector<ll> dp1(n + 1, -1);
	vector<map<int, ll>> dp2(n + 1);
	priority_queue<pair<pair<ll, int>, pair<bool, int>>> djk;
	djk.push({ {0, 1}, {false, 0} });
	while (!djk.empty())
	{
		ll d = -djk.top().first.first;
		int node = djk.top().first.second, lstc = djk.top().second.second;
		bool dp12 = djk.top().second.first;
		djk.pop();
		if (!dp12) if (dp1[node] == -1)
		{
			dp1[node] = d;
			for (auto edgset : adj[node]) for (pair<ll, int> nxt : edgset.second.first)
			{
				djk.push({ {-d, nxt.second}, {true, edgset.first} });
				djk.push({ {-d - nxt.first, nxt.second}, {false, edgset.first} });
				djk.push({ {-d - (edgset.second.second - nxt.first), nxt.second},{false, edgset.first} });
			}
		}

		if (dp12) if (dp2[node].count(lstc) == 0)
		{
			dp2[node][lstc] = d;
			for (pair<ll, int> nxt : adj[node][lstc].first) djk.push({ {-d - (adj[node][lstc].second - nxt.first), nxt.second}, {false, lstc} });
		}
	}

	cout << dp1[n];
}

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