Submission #448582

#	Time	Username	Problem	Language	Result	Execution time	Memory
448582		training4usaco	Robot (JOI21_ho_t4)	C++11	0 / 100	297 ms	35228 KiB

Main

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <climits>

using namespace std;
using ll = long long;

#define INF 1e18
#define MAXN 100001

struct Edge {
	int to;
    int color;
	ll price;
};

int n, m;
vector<map<int, vector<Edge>>> adj(MAXN);
vector<ll> dp(MAXN, INT_MAX);
vector<map<int, ll>> dp2(MAXN);
vector<map<int, ll>> cum(MAXN);

int main() {
	cin >> n >> m;

	for (int i = 0; i < m; ++i) {
		int u, v, color;
		ll price;
		cin >> u >> v >> color >> price;
		adj[u][color].push_back({v, color, price});
		adj[v][color].push_back({u, color, price});
		cum[u][color] += price;
		cum[v][color] += price;
	}

	dp[1] = 0;
    
	priority_queue<pair<ll, pair<int, int>>, vector<pair<ll, pair<int, int>>>, greater<pair<ll, pair<int, int>>>> pq;

	pq.push({0, {1, 0}});
	while (!pq.empty()) {
		ll price = pq.top().first;
		int node = pq.top().second.first;
        int color = pq.top().second.second;
		pq.pop();

		if (color != 0) {
			if (dp2[node][color] != price) {
                continue;
            }
			for (Edge next : adj[node][color]) {
				// we can't flip edge in this case
				ll opt1 = cum[node][color] + next.price;

				if (opt1 + price < dp[next.to]) {
					dp[next.to] = opt1 + price;
					pq.push({dp[next.to], {next.to, 0}});
				}
			}
		} 
        else {
			if (dp[node] != price) {
                continue;
            }
            
			for (auto& i : adj[node]) {
				for (Edge j : i.second) {
					// dont flip j
					ll opt1 = cum[node][j.color] + j.price + price;
					if (opt1 < dp[j.to]) {
						dp[j.to] = opt1;
						pq.push({dp[j.to], {j.to, 0}});
					}
					// flip j but not another edge of the same colour
					ll opt2 = j.price + price;
					if (opt2 < dp[j.to]) {
						dp[j.to] = opt2;
						pq.push({dp[j.to], {j.to, 0}});
					}
					// flip j and another edge of the same colour
					ll opt3 = price;
					if (!dp2[j.to].count(j.color) || opt3 < dp2[j.to][j.color]) {
						dp2[j.to][j.color] = opt3;
						pq.push({dp2[j.to][j.color], {j.to, j.color}});
					}
				}
			}
		}
	}
    if(dp[n] >= INF) {
        cout << -1 << endl;
        return 0;
    }
    cout << dp[n] << endl;
	return 0;
}

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