oj.uz

Submission #942107

# Submission time Handle Problem Language Result Execution time Memory
942107 2024-03-10T09:17:13 Z dsyz Robot (JOI21_ho_t4) C++17
0 / 100
 49 ms 12724 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 12724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -