Submission #942107

#	Time	Username	Problem	Language	Result	Execution time	Memory
942107		dsyz	Robot (JOI21_ho_t4)	C++17	0 / 100	49 ms	12724 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,M;
	cin>>N>>M;
	vector<pair<ll,ll> > v[N];
	map<ll,ll> colourcnt[N];
	for(ll i = 0;i < M;i++){
		ll a,b,c,p;
		cin>>a>>b>>c>>p;
		a--, b--, c--;
		v[a].push_back({b,c});
		v[b].push_back({a,c});
		colourcnt[a][c]++;
		colourcnt[b][c]++;
	}
	priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > pq;
	ll dist[N];
	memset(dist,-1,sizeof(dist));
	dist[0] = 0;
	pq.push({0,0});
	while(!pq.empty()){
		ll d = pq.top().first;
		ll x = pq.top().second;
		pq.pop();
		if(d != dist[x]){
			continue;
		}
		for(auto u : v[x]){
			ll w = colourcnt[x][u.second] - 1;
			if(dist[u.first] == -1 || dist[u.first] > dist[x] + w){
				dist[u.first] = dist[x] + w;
				pq.push({dist[u.first],u.first});
			}
		}
	}
	if(dist[N - 1] == -1){
		cout<<-1<<'\n';
	}else{
		cout<<dist[N - 1]<<'\n';
	}
}

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