Submission #493854

#	Time	Username	Problem	Language	Result	Execution time	Memory
493854		PixelCat	Robot (JOI21_ho_t4)	C++14	100 / 100	467 ms	66476 KiB

Main

#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Forr(i,a,b) for(int i=a;i>=b;i--)
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define INF (ll)(9e18)
#define int ll
using namespace std;
using ll=long long;
using pii=pair<int,int>;

// color -> vector( (to,cost) )
map<int,vector<pii>> adj[100010];

vector<pii> g[100010];
int dist[100010];
bool vis[100010];

int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	// nachoneko sama & miku sama bless me >/////<
	int n,m; cin>>n>>m;
	For(i,1,m){
		int a,b,c,p; cin>>a>>b>>c>>p;
		adj[a][c].eb(b,p);
		adj[b][c].eb(a,p);
	}
	For(i,1,n){
		for(auto &item:adj[i]){
			auto &ad=item.S;
			if(sz(ad)==1){
				g[i].eb(ad[0].F,0ll);
				continue;
			}
			
			sort(all(ad),[](const pii &a,const pii &b){
				return a.S>b.S;
			});
			int tot=0;
			for(auto &j:ad) tot+=j.S;

			for(auto &j:ad){
				g[i].eb(j.F,j.S);
			}
			
			// leave the biggest edge, change the rest
			g[i].eb(ad[0].F,tot-ad[0].S);
			For(iter,1,sz(ad)-1){
				g[ad[iter].F].eb(ad[0].F,tot-ad[0].S);
			}

			// leave the 2nd biggest edge, change the rest
			g[i].eb(ad[1].F,tot-ad[1].S);
			For(iter,0,sz(ad)-1) if(iter!=1){
				g[ad[iter].F].eb(ad[1].F,tot-ad[1].S);
			}
		}
	}
	// dijkstra on g[]
	For(i,1,n) dist[i]=INF;
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	pq.emplace(0,1);
	while(!pq.empty()){
		int d=pq.top().F;
		int now=pq.top().S;
		pq.pop();
		if(vis[now]) continue;
		vis[now]=true;
		for(auto &e:g[now]){
			if(d+e.S<dist[e.F]){
				pq.emplace(d+e.S,e.F);
				dist[e.F]=d+e.S;
			}
		}
	}
	if(dist[n]==INF) cout<<"-1\n";
	else cout<<dist[n]<<"\n";
	return 0;
}

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