Submission #467807

#	Time	Username	Problem	Language	Result	Execution time	Memory
467807		Autron	Robot (JOI21_ho_t4)	C++14	100 / 100	1361 ms	131648 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long

int n, m;

struct edge{
	int to, c, p;
};

struct nod{
	unordered_map<int, vector<edge>> out;
	int dp;
	bool used;
	unordered_map<int, int> dpc;
	unordered_map<int, bool> usedc;
	unordered_map<int, int> sum;
};

struct elem{
	int cost, x, c;
	
	bool operator<(const elem &ot) const{
		return cost>ot.cost;
	}

};

vector<nod> g;


int32_t main(){
	cin>>n>>m;
	g.resize(n+1);
	for(int i=1;i<=m;++i){
		int a, b, c, p;
		cin>>a>>b>>c>>p;
		g[a].out[c].push_back({b, c, p});
		g[b].out[c].push_back({a, c, p});
		g[a].sum[c]+=p;
		g[b].sum[c]+=p;
	}

	priority_queue<elem> pq;
	for(int i=1;i<=n;++i) g[i].dp=1e18;
	g[1].dp=0;
	pq.push({0, 1, 0});
	while(!pq.empty()){
		elem x=pq.top();
		pq.pop();
		if(x.c){
			if(g[x.x].usedc.count(x.c)) continue;
			g[x.x].usedc[x.c]=1;
			for(auto it:g[x.x].out[x.c]){
				int cost=g[x.x].sum[x.c]-it.p+x.cost;	
				if(cost<g[it.to].dp){
					g[it.to].dp=cost;
					pq.push({g[it.to].dp, it.to, 0});
				}
			}
		}
		else{
			if(g[x.x].used) continue;
			g[x.x].used=1;		
			for(auto out:g[x.x].out){
				for(auto it:out.second){
					int cost=g[x.x].sum[it.c]-it.p+x.cost;	
					if(cost<g[it.to].dp){
						g[it.to].dp=cost;
						pq.push({g[it.to].dp, it.to, 0});
					}
					cost=it.p+x.cost;
					if(cost<g[it.to].dp){
						g[it.to].dp=cost;
						pq.push({g[it.to].dp, it.to, 0});
					}
					cost=x.cost;
					if((!g[it.to].dpc.count(it.c))||(cost<g[it.to].dpc[it.c])){
						g[it.to].dpc[it.c]=cost;
						pq.push({g[it.to].dpc[it.c], it.to, it.c});
					}
				}
			}
		}
	}
	int sol=g[n].dp;
	if(sol==1e18) sol=-1;
	cout<<sol<<"\n";

}

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