Submission #1288015

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288015		WH8	Robot (JOI21_ho_t4)	C++20	0 / 100	3094 ms	75164 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define ld long double
#define sz(x) static_cast<int>((x).size())
#define i5 tuple<int,int,int,int,int>

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,e;cin>>n>>e;
	vector<tuple<int,int,int,int>> ed={{0, 1, 0, 0}};
	vector<map<int,int>> m(n+1);
	vector<vector<int>> al(n+1);
	for(int i=0;i<e;i++){
		int a,b,c,p;cin>>a>>b>>c>>p;
		al[a].pb(ed.size());
		ed.pb({a, b, c, p});
		al[b].pb(ed.size());
		ed.pb({b, a, c, p});
		m[a][c]+=p;
	
		m[b][c]+=p;
	}
	int sz=ed.size();
	for(int i=1;i<sz;i++){
		auto [a,b,c,p] = ed[i];
		ed.pb({0,b,0,0});
	}
	vector<int> dist(ed.size()+1, 1e15);
	priority_queue<i5, vector<i5>, greater<i5>> pq;
	pq.push({0, 1, 0, 0, sz+1});
	dist[sz+1]=0;
	int ans=1e15;
	while(!pq.empty()){
		auto [cd, cur, fc, fp, edind] = pq.top(); pq.pop();
		if(cur==n){
			ans=min(ans, cd);
		}
		if(dist[edind] < cd) continue;
		for(auto toi : al[cur]){
			auto [_, to, tc, tp] = ed[toi];
			int cost;
			// change edge colour. 
			cost=tp;
			if(cd + cost >= dist[toi])continue;
			dist[toi]=cd+cost;
			pq.push({dist[toi], to, tc, tp, toi}); 
			//~ printf("change edge col, at %lld, fc %lld, going to %lld, cost is %lld\n", cur, fc, to, cost);

			// dont change edge colour.
			cost= max(0ll, m[cur][tc]-(tc==fc? fp : 0)-tp);
			if(cd + cost >= dist[sz+to])continue;
			dist[sz+to]=cd+cost;
			pq.push({dist[sz+to], to, 0, 0, sz+to}); 
			//~ printf("dont change, at %lld, fc %lld, going to %lld, cost is %lld\n", cur, fc, to, cost);
		}
	}
	if(ans >= 1e15){
		cout<<-1;
	}
	else cout<<ans;
	
}
/*
6 6
1 2 1 1 
2 3 1 1 
2 4 1 1
3 5 1 1 
4 5 1 1 
5 6 1 1 
 
*/

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