제출 #937329

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
937329		amirhoseinfar1385	Robot (JOI21_ho_t4)	C++17	100 / 100	1420 ms	111068 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const long long maxn=100000+10,maxm=200000+10;
struct yal{
	long long u,v,c,w;
	long long getad(long long fu){
		return (u^v^fu);
	}
}alle[maxm];
long long n,m,vis[maxn];
long long mainres=-1;
vector<long long>adj[maxn];
map<long long,long long>sum[maxn];
map<long long,vector<long long>>all[maxn];
void vorod(){
	cin>>n>>m;
	for(long long i=0;i<m;i++){
		cin>>alle[i].u>>alle[i].v>>alle[i].c>>alle[i].w;
		adj[alle[i].u].push_back(i);
		adj[alle[i].v].push_back(i);
		sum[alle[i].u][alle[i].c]+=alle[i].w;
		sum[alle[i].v][alle[i].c]+=alle[i].w;
		all[alle[i].u][alle[i].c].push_back(i);
		all[alle[i].v][alle[i].c].push_back(i);
	}
}
set<pair<long long,pair<long long,long long>>>st;

void aval(long long u,long long w){
	for(auto x:adj[u]){
		long long v=alle[x].getad(u);
		st.insert(make_pair(w+min(alle[x].w,sum[u][alle[x].c]-alle[x].w),make_pair(v,-1)));
		st.insert(make_pair(w,make_pair(v,x)));
	}
}

void upd(long long u,long long ind,long long w){
	if(ind==-1){
		return ;
	}
	long long f=0;
	for(auto x:all[u][alle[ind].c]){
		if(x==ind){
			f=1;
			continue;
		}
		long long v=alle[x].getad(u);
		st.insert(make_pair(w+sum[u][alle[x].c]-alle[x].w,make_pair(v,-1)));
	}
	all[u][alle[ind].c].clear();
	if(f){
		all[u][alle[ind].c].push_back(ind);
	}
}

void solve(){
	aval(1,0);
	vis[1]=1;
	while((long long)st.size()>0){
		auto x=*st.begin();
		st.erase(x);
		long long u=x.second.first,w=x.first,from=x.second.second;
		if(x.second.first==n&&from==-1){
			mainres=x.first;
			return ;
		}
		if(vis[u]==0&&from==-1){
			aval(u,w);
			vis[u]=1;
		}
		upd(u,from,w);
	}
}

void khor(){
	cout<<mainres<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
//	freopen("inp.txt","r",stdin);
	vorod();
	solve();
	khor();
}

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