Submission #937327

#	Time	Username	Problem	Language	Result	Execution time	Memory
937327		amirhoseinfar1385	Robot (JOI21_ho_t4)	C++17	0 / 100	4 ms	12892 KiB

Main

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

void aval(int u,int w){
	for(auto x:adj[u]){
		int 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(int u,int ind,int w){
	if(ind==-1){
		return ;
	}
	int f=0;
	for(auto x:all[u][alle[ind].c]){
		if(x==ind){
			f=1;
			continue;
		}
		int 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((int)st.size()>0){
		auto x=*st.begin();
		st.erase(x);
		int 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();
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:83:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |  freopen("inp.txt","r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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