Submission #385495

#	Time	Username	Problem	Language	Result	Execution time	Memory
385495		ngpin04	Robot (JOI21_ho_t4)	C++14	34 / 100	3091 ms	31440 KiB

Main

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
struct edge {
	int v,pos,c,cost;
	edge(){}
	edge(int _v, int _pos, int _c, int _cost) {
		v = _v;
		pos = _pos;
		c = _c;
		cost = _cost;
	}
};

const int N = 1e5 + 5;
const int M = 2e5 + 5;
const long long oo = 1e18;

vector <edge> adj[N];

vector <long long> dis[N];

long long sum[M];

int n,m;

template <typename T> 
bool mini(T &a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u,v,c,w;
		cin >> u >> v >> c >> w;
		edge a = edge(v, adj[v].size(), c, w);
		edge b = edge(u, adj[u].size(), c, w);
		adj[u].push_back(a);
		adj[v].push_back(b);
	}

	for (int i = 1; i <= n; i++) 
		dis[i].assign(adj[i].size() + 1, oo);
	
	priority_queue <pair <long long, pair <int, int>>> heap;
	heap.push(mp(0, mp(1, adj[1].size())));
	dis[1][adj[1].size()] = 0;

	while (heap.size()) {
		int u = heap.top().se.fi;
		int id = heap.top().se.se;	
		long long cur = -heap.top().fi;
		heap.pop();
		if (cur != dis[u][id])
			continue;
		//cerr << u << " " << id << endl;
		for (int i = 0; i < (int) adj[u].size(); i++) if (i != id) {
			edge e = adj[u][i];
			sum[e.c] += e.cost;
		}

		for (int i = 0; i < (int) adj[u].size(); i++) if (i != id) {
			edge e = adj[u][i];
			int v = e.v;
			int c = e.c;
			int pos = e.pos;
			int cost = e.cost;

			if (mini(dis[v][pos], cur + cost)) 
				heap.push(mp(-dis[v][pos], mp(v, pos)));
		
			if (mini(dis[v][adj[v].size()], cur + sum[c] - cost))
				heap.push(mp(-dis[v][adj[v].size()], mp(v, adj[v].size())));
		}

		for (edge e : adj[u])
			sum[e.c] = 0;
	}
	long long ans = oo;
	for (long long res : dis[n])
		ans = min(ans, res);
	if (ans == oo)
		ans = -1;
	cout << ans;
	return 0;
}

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