Submission #935006

#	Time	Username	Problem	Language	Result	Execution time	Memory
935006		BF001	Robot (JOI21_ho_t4)	C++17	100 / 100	974 ms	97812 KiB

Main

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

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

typedef pair<int, pair<int, pair<int, int>>> iii;

struct ii
{	
	int v, c, cst;
};



int n, d[N], m, cle[M], u[M], v[M], cl[M], cst[M];
vector<int> adj[N];
map<int, int> sum[N], d2[N];
map<int, vector<int>> adj2[N];

void ditra(){
	for (int i = 1; i <= n; i++){
		d[i] = oo;
	}
	priority_queue<iii, vector<iii>, greater<iii>> q;
	d[1] = 0;
	q.push({0, {1, {0, 0}}});
	while (!q.empty()){
		int du = q.top().fi;
		int uu = q.top().se.fi;
		int typ = q.top().se.se.se;
		int laste = q.top().se.se.fi;
		q.pop();
		if (typ){
			if (d2[uu][typ] != du) continue;
				for (auto x : adj2[uu][typ]){
				int vv = v[x];
				if (vv == uu) vv = u[x];
				int d3 = sum[uu][typ] - cst[x] + du;
				if (d3 < d[vv]){
					d[vv] = d3;
					q.push({d3, {vv, {x, 0}}});
				}
			}
		}
		else {
			if (d[uu] != du) continue;
			for (auto x : adj[uu]){
				int vv = v[x];
				if (vv == uu) vv = u[x];
				int cost = cst[x];
				int clr = cl[x];
				int d1 = du + sum[uu][clr] - cost;
				if (d1 < d[vv]){
					d[vv] = d1;
					q.push({d1, {vv, {x, 0}}});
				}
				int d22 = du + cost;
				if (d22 < d[vv]){
					d[vv] = d22;
					q.push({d22, {vv, {x, 0}}});
				}
				int d3 = du;
				if (d2[vv].count(clr) == 0 || d3 < d2[vv][clr]){
					d2[vv][clr] = d3;
					q.push({d3, {vv, {x, clr}}});
				}
			}
		}
	}
}

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, cst;
    	cin >> u[i] >> v[i] >> cl[i] >> cst[i];
    	adj[u[i]].push_back(i);
    	adj[v[i]].push_back(i);
    	sum[u[i]][cl[i]] += cst[i];
    	sum[v[i]][cl[i]] += cst[i];
    	adj2[u[i]][cl[i]].push_back(i);
    	adj2[v[i]][cl[i]].push_back(i);
    }

    ditra();

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

}     

Compilation message (stderr)

Main.cpp: In function 'void ditra()':
Main.cpp:36:7: warning: unused variable 'laste' [-Wunused-variable]
   36 |   int laste = q.top().se.se.fi;
      |       ^~~~~

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