Submission #478040

#	Time	Username	Problem	Language	Result	Execution time	Memory
478040		lequocbinh	Robot (JOI21_ho_t4)	C++17	0 / 100	465 ms	41688 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
# define TASK ""
# define FOR(i,x,y) for(int i = x; i <= y; ++i)
# define all(x) x.begin(), x.end()
# define pii pair< ll , pair< ll, ll > >
template <class T>
bool inArr(T obj, vector<T> x){
	return find(all(x), obj) != x.end();
}

int getbit(int i, int j){
	return ( 1 << (j-1) ) & i;
}

const long long MAXN = 1e5 + 5;
ll N, M;
struct binh{
	ll v,c,p;
};	
vector< binh > g[MAXN];
map < ll , ll > m[MAXN];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	if(fopen(TASK".inp", "r")){
		freopen(TASK".inp", "r", stdin);
		freopen(TASK".out", "w", stdout);
	}

	cin >>N >> M;
	for(int i = 1; i <= M; ++i){
		ll u,v,c,p;
		cin >> u >> v >> c >> p;
		g[u].push_back({v,c,p});
		g[v].push_back({u,c,p});
		++m[u][c];
		++m[v][c];
	}


	priority_queue< pii, vector< pii >, greater< pii > > q;
	q.push({0, {1, 0}});

	vector< ll > d(N + 1, LLONG_MAX);
	vector< ll > vis(N + 1, 0);
	d[1] = 0;
	while(q.size()){
		ll cost = q.top().first;
		ll u = q.top().second.first;
		ll c = q.top().second.second;
		q.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		if(c){
			m[u][c]--;
		}
		for(auto [v, c, p] : g[u]){
			if(m[u][c] == 1){
				d[v] = min(d[v], cost);
				q.push({cost, {v, 0}});
			}
			else if(d[v] > cost + p){
				q.push({d[v] = cost + p, {v, c}});
			}
		}
	}

	if(d[N] != LLONG_MAX) cout << d[N]; else cout << -1;

	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:31:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |   freopen(TASK".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:32:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |   freopen(TASK".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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