Submission #936836

#	Time	Username	Problem	Language	Result	Execution time	Memory
936836		vjudge1	Robot (JOI21_ho_t4)	C++17	24 / 100	1116 ms	87256 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;
const int logo = 20;
const int off = 1 << logo;


map<int, vii> g[MAXN];
vii adj[MAXN];

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

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});
	}
	
	for(int i=1; i<=n; i++){
		for(auto &x : g[i]){
			dis[i][x.X] = INF;
			s.insert({dis[i][x.X], {i, x.X}});
		}
		if(i == 1) dis[i][0] = 0;
		else dis[i][0] = INF;
		s.insert({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 << cr.X << "\n";
			return;
		}
		
		if(col == 0){
			for(auto &x : g[u]){
				for(auto &y : x.Y){						
					int v = y.X, tez = y.Y, b = x.X;
					
					if(x.Y.size() == 1) tez = 0;
					
					ll nd = d + tez;
					if(nd < dis[v][0]){
						s.erase({dis[v][0], {v, 0}});
						dis[v][0] = nd;
						s.insert({dis[v][0], {v, 0}});
					}
					
					nd = d;
					if(nd < dis[v][b]){
						s.erase({dis[v][b], {v, b}});
						dis[v][b] = nd;
						s.insert({dis[v][b], {v, b}});
					}
				}
			}
		}else{
			ll csu = 0;
			for(auto &x : g[u][col]) csu += x.Y;
			
			for(auto &x : g[u][col]){
				ll tez = csu - x.Y;
				int v = x.X;
				ll nd = tez + d;
				if(nd < dis[v][0]){
					s.erase({dis[v][0], {v, 0}});
					dis[v][0] = nd;
					s.insert({dis[v][0], {v, 0}});
				}
				
				if(nd < dis[v][col]){
					s.erase({dis[v][col], {v, col}});
					dis[v][col] = nd;
					s.insert({dis[v][col], {v, col}});
				}
			}
		}
	}
}

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: 0 / 34
• Subtask 2: 24 / 24
• Subtask 3: 0 / 42