Submission #1288035

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288035		WH8	Robot (JOI21_ho_t4)	C++20	34 / 100	3097 ms	67012 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>> inpe;
	vector<tuple<int,int,int,int,int>> 	ed={{0, 1, e,e, 0}};
	vector<vector<int>> disc(n+1);
	vector<vector<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;
		inpe.pb({a,b,c,p});
		disc[a].pb(c);
		disc[b].pb(c);
	}
	for(int i=1;i<=n;i++){
		sort(disc[i].begin(),disc[i].end());
		disc[i].erase(unique(disc[i].begin(),disc[i].end()),disc[i].end());
	}
	for(auto [a,b,c,p]:inpe){
		al[a].pb(ed.size());
		int inb=lower_bound(disc[b].begin(),disc[b].end(),c)-disc[b].begin();
		int ina=lower_bound(disc[a].begin(),disc[a].end(),c)-disc[a].begin();

		ed.pb({a, b, ina, inb, p});
		al[b].pb(ed.size());
		ed.pb({b, a, inb, ina, p});
		m[a].resize(disc[a].size(),0);
		m[b].resize(disc[b].size(),0);
		m[a][ina]+=p;
		m[b][inb]+=p;
	}
	int sz=ed.size();
	for(int i=1;i<=n;i++){
		ed.pb({0, i, e,e, 0});
	}
	//~ for(auto [a,b,c,d,p] : ed){
		//~ cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<p<<endl;
	//~ }
	vector<int> dist(ed.size()+1, 1e15);
	priority_queue<i5, vector<i5>, greater<i5>> pq;
	pq.push({0, 1, e, 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, curc, tc, tp] = ed[toi];
			int cost;
			// change edge colour. 
			cost=tp;
			if(cd + cost < dist[toi]){
				dist[toi]=cd+cost;
				pq.push({dist[toi], to, disc[to][tc], tp, toi}); 
				//~ printf("change edge col, at %lld cd %lld, fc %lld, going to %lld, cost is %lld\n"
				//~ , cur, cd, fc, to, cost);
			}

			// dont change edge colour.
			cost= max(0ll, m[cur][curc]-(disc[to][tc]==fc? fp : 0)-tp);
			if(cd + cost < dist[sz+to]){	
				dist[sz+to]=cd+cost;
				pq.push({dist[sz+to], to, e, 0, sz+to}); 
				//~ printf("dont change, m[cur][%lld] is %lld, at %lld, cd %lld,  fc %lld, going to %lld, cost is %lld\n", 
				//~ curc, m[cur][curc],cur, cd, fc, to, cost);
			}
		}
		//~ for(int i=1;i<ed.size();i++){
			//~ cout<<dist[i]<<" ";
		//~ }
		//~ cout<<endl;
	}
	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 
 
6 6

4 3 
1 2 1 3 
2 3 1 4 
3 4 1 3

1 4 2 6
4 5 3 5 
5 6 3 5
*/

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