제출 #493837

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
493837		nathanlee726	Robot (JOI21_ho_t4)	C++14	0 / 100	397 ms	132784 KiB

Main

#include<bits/stdc++.h>
using namespace std; 
#define ll long long
#define int ll
#define pii pair<int,int>
#define X first
#define Y second
#define F(n) Fi(i,n) 
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define abs(x) ((x)>0?(x):-(x))
#define pb push_back

int n,m,ind,rr[2000010],d[2000010];
vector<pair<pii,pii> >g[2000010],rg[2000010];
map<pii,int> mmp;
bool used[2000010];

void calc(int x){
	map<int,int> mp;
	for(auto pt:g[x]){
		mp[pt.X.Y]+=pt.Y.X;
	}
	F(sz(g[x])){
		g[x][i].Y.Y=mp[g[x][i].X.Y]-g[x][i].Y.X;
	}
}

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;
	ind=n;
	F(m){
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		--a,--b;
		g[a].pb({{b,c},{d,0}});
		g[b].pb({{a,c},{d,0}});
	}
	F(n)calc(i);
	vector<int> v;
	F(n){
		int tt=sz(g[i]);
		Fi(j,tt){
			if(!mmp.count(g[i][j].X)){if(g[i][j].X.X==n-1)v.pb(ind);mmp[g[i][j].X]=ind++;}
			int ttt=mmp[g[i][j].X];
			//cout<<"CCC "<<ttt<<endl;
			g[i].pb({{ttt,g[i][j].X.Y},{g[i][j].Y.X,g[i][j].Y.Y}});
			g[ttt].pb({{i,g[i][j].X.Y},{g[i][j].Y.X,0}});
		}
	}
	for(int i=n;i<ind;i++)calc(i);
	for(int i=n;i<ind;i++){
		int tt=sz(g[i]);
		Fi(j,tt){
			pair<pii,pii> pt=g[i][j];
			int u=mmp[pt.X];
			pii ptt=pt.Y;
			ptt.Y=max(0ll,ptt.Y-1);
			g[i].pb({{u,-1},ptt});
		}
	}
	
	F(ind)d[i]=1e18;
	priority_queue<pii,vector<pii>,greater<pii> >pq;
	pq.push({0,0});
	memset(used,0,sizeof(used));
	while(!pq.empty()){
		int p=pq.top().Y,ss=pq.top().X;pq.pop();
		if(used[p])continue;
		d[p]=ss;
		//cout<<"a "<<p<<" "<<ss<<endl;
		used[p]=1;
		for(auto pt:g[p]){
			if(pt.X.X>=n){
				pq.push({ss+pt.Y.X,pt.X.X});
			}
			else{
			//	cout<<"cc "<<pt.Y.Y<<" "<<pt.X.X<<endl;
				if(pt.Y.Y<=1)pq.push({ss+pt.Y.Y,pt.X.X});
			}
		}
	}
	v.pb(n-1);
	//for(auto pt:g[0])cout<<pt.X.X<<" "<<pt.X.Y<<" "<<pt.Y.X<<" "<<pt.Y.Y<<endl;
	int ans=1e18;
	for(int i:v)ans=min(ans,d[i]);
	cout<<(ans>1e17?-1:ans)<<endl;
	return 0;
}

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