Submission #936849

#	Time	Username	Problem	Language	Result	Execution time	Memory
936849		jcelin	Robot (JOI21_ho_t4)	C++14	100 / 100	1481 ms	104228 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#define PB push_back
#define X first
#define Y second

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;

const int MAXN = 1e5 + 7;
const ll INF = 1e18 + 7;


map<int, vii> g[MAXN];
set<pair<ll, ii>> s;
map<int, ll> dis[MAXN], su[MAXN];


void upd(int x, int col, ll nd){
	if(dis[x][col] <= nd) return;
	s.erase({dis[x][col], {x, col}});
	dis[x][col] = nd;
	s.insert({dis[x][col], {x, col}});
}

void solve(){
	int n, m;
	cin >> n >> m;
	for(int i=0; i<m; i++){
		int a, b, c, p;
		cin >> a >> b >> c >> p;
		g[a][c].PB({b, p});
		g[b][c].PB({a, p});
		su[a][c] += p;
		su[b][c] += p;
	}
	
	for(int i=1; i<=n; i++){
		for(auto &x : g[i]){
			dis[i][x.X] = INF;
			s.insert({(ll)dis[i][x.X], {i, x.X}});
		}
		if(i == 1) dis[i][0] = 0;
		else dis[i][0] = INF;
		s.insert({(ll)dis[i][0], {i, 0}});
	}
	
	
	while(!s.empty()){
		pair<ll, ii> cr = *s.begin();
		s.erase(s.begin());
		int u = cr.Y.X, col = cr.Y.Y;
		ll d = cr.X;
		
		if(u == n and col == 0){
			if(cr.X >= INF) cout << -1 << "\n";
			else cout << d << "\n";
			return;
		}
		
		if(col == 0){
			for(auto &x : g[u]){
				for(auto &y : x.Y){						
					int v = y.X, b = x.X;
					ll tez = y.Y;
					tez = min(tez, su[u][b] - tez);
					ll nd = d + (ll)tez;
					upd(v, 0, nd);
					upd(v, b, d);
				}
			}
		}else{
			if(g[u][col].size() == 1) continue;
			for(auto &x : g[u][col]){
				ll tez = su[u][col] - (ll)x.Y;
				int v = x.X;
				ll nd = d + (ll)tez;
				upd(v, 0, nd);
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int tt = 1;
	//cin >> tt;
	while(tt--) solve();
	return 0;
}

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