Submission #988326

#	Time	Username	Problem	Language	Result	Execution time	Memory
988326		BF001	Robot (JOI21_ho_t4)	C++17	100 / 100	1188 ms	95460 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define N 100005
#define M 200005
#define fi first
#define se second
#define oo 1e18

typedef pair<int, pair<int, int>> ii;

int n, m, d[N], ua[M], va[M], cla[M], pa[M]; 
vector<int> adj[N];
map<int, int> sum[N], d2[N];
map<int, vector<int>> dj[N];

void ditra(){
	priority_queue<ii, vector<ii>, greater<ii>> q;
	for (int i = 1; i <= n; i++) d[i] = oo;
	d[1] = 0;
	q.push({0, {1, 0}});
	while (!q.empty()){
		int du = q.top().fi;
		int u = q.top().se.fi;
		int typ = q.top().se.se;
		q.pop();
		if (typ){
			if (d2[u][typ] != du) continue;
			for (auto x : dj[u][typ]){
				int v = va[x];
				if (v == u) v = ua[x];
				int dis = du + sum[u][typ] - pa[x];
				if (d[v] > dis){
					d[v] = dis;
					q.push({d[v], {v, 0}});
				}
			}
			continue;
		}
		if (d[u] != du) continue;
		for (auto x : adj[u]){
			int v = va[x];
			if (v == u) v = ua[x];
			int d1 = du + sum[u][cla[x]] - pa[x];
			if (d1 < d[v]){
				d[v] = d1;
				q.push({d1, {v, 0}});
			}
			d1 = du + pa[x];
			if (d1 < d[v]){
				d[v] = d1;
				q.push({d1, {v, 0}});
			}
			d1 = du;
			if (d2[v].find(cla[x]) == d2[v].end() || d2[v][cla[x]] > d1){
				d2[v][cla[x]] = d1;
				q.push({d1, {v, cla[x]}});
			}
		}
	}
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
        
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
    	int u, v, c, p;
    	cin >> u >> v >> c >> p;
    	ua[i] = u; va[i] = v; cla[i] = c; pa[i] = p;
    	adj[u].push_back(i);
    	adj[v].push_back(i);
    	dj[u][c].push_back(i);
    	dj[v][c].push_back(i);
    	sum[u][c] += p;
    	sum[v][c] += p;
    }

    ditra();

    if (d[n] >= oo) cout << -1;
    else cout << d[n];

    return 0;
}     

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