Submission #444777

#	Time	Username	Problem	Language	Result	Execution time	Memory
444777		dutch	Robot (JOI21_ho_t4)	C++17	100 / 100	1103 ms	85928 KiB

Main

#include <bits/stdc++.h>
#define int int64_t
using namespace std;
 
const int LIM = 1e5, INF = 1e18;

class comp{
public:
	bool operator()(array<int, 3> &x, array<int, 3> &y){ return x[0] > y[0]; }
};

map<int, int> d[LIM], s[LIM];
map<int, vector<array<int, 2>>> g[LIM];
priority_queue<array<int, 3>, vector<array<int, 3>>, comp> q;


void add(int i, int j, int k){
	if(d[i][k] > j) q.push({d[i][k] = j, i, k});
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int n, m; cin >> n >> m;
	for(int i=0; i<m; ++i){
		int u, v, c, w; cin >> u >> v >> c >> w;
		--u, --v;
		g[u][c].push_back({v, w});
		g[v][c].push_back({u, w});
		s[u][c] += w;
		s[v][c] += w;
		d[u][c] = d[v][c] = INF;
	}
 
 	for(int u=0; u<n; ++u) d[u][0] = INF;
	q.push({d[0][0] = 0, 0});
 
	while(!q.empty()){
		int dist = q.top()[0], u = q.top()[1], c = q.top()[2];
		q.pop();
		if(dist != d[u][c]) continue;
 		
 		if(c){
 			for(auto &[v, w] : g[u][c])
 				if(s[u][c] - w >= 0)
 					add(v, dist + s[u][c] - w, 0);
 		}else{
 			for(auto &h : g[u])
 				for(auto &[v, w] : h.second){
 					add(v, dist + min(s[u][h.first] - w, w), 0);
 					add(v, dist, h.first);
 				}
 		}
	}
	cout << (d[n-1][0] == INF ? -1 : d[n-1][0]);
}

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