Submission #1226252

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226252		boclobanchat	Robot (JOI21_ho_t4)	C++20	58 / 100	3098 ms	262056 KiB

Main

#include<bits/stdc++.h>
using namespace std;
struct edge { int pos,id,val; };
bool comp(edge a,edge b) { return a.id<b.id; }
const int MAXN=17e5+5;
const long long INF=1e18;
map< pair<int,int>,int > mp[2];
vector<edge> ds[MAXN];
vector< pair<int,long long> > E[MAXN];
long long dp[MAXN];
int pos[MAXN];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int l,r,c,v;
		cin>>l>>r>>c>>v;
		ds[l].push_back({r,c,v}),ds[r].push_back({l,c,v});
	}
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		pos[i]=++cnt;
		int sz=ds[i].size(),pre=0;
		sort(ds[i].begin(),ds[i].end(),comp);
		for(int j=1;j<=sz;j++) if(j==sz||ds[i][j].id!=ds[i][j-1].id)
		{
			long long sum=0;
			for(int k=pre;k<j;k++) sum+=ds[i][k].val;
			for(int k=pre;k<j;k++)
			{
				E[pos[i]].push_back({mp[0][{i,ds[i][k].pos}]=++cnt,ds[i][k].val});
				E[pos[i]].push_back({mp[1][{i,ds[i][k].pos}]=++cnt,sum-ds[i][k].val});
			}
			pre=j;
		}
	}
	for(int i=1;i<=n;i++) for(auto v:ds[i])
	{
		E[mp[0][{i,v.pos}]].push_back({pos[v.pos],0});
		E[mp[1][{i,v.pos}]].push_back({pos[v.pos],0});
	}
	for(int i=1;i<=n;i++)
	{
		int sz=ds[i].size(),pre=0;
		for(int j=1;j<=sz;j++) if(j==sz||ds[i][j].id!=ds[i][j-1].id)
		{
			long long sum=0;
			for(int k=pre;k<j;k++) sum+=ds[i][k].val;
			for(int k=pre;k<j;k++)
			{
				E[++cnt].push_back({pos[ds[i][k].pos],sum-ds[i][k].val});
				if(k>pre) E[cnt].push_back({cnt-2,0}),E[mp[0][{ds[i][k].pos,i}]].push_back({cnt-2,-ds[i][k].val});
				E[++cnt].push_back({pos[ds[i][k].pos],sum-ds[i][k].val});
				if(k<j-1) E[cnt].push_back({cnt+2,0}),E[mp[0][{ds[i][k].pos,i}]].push_back({cnt+2,-ds[i][k].val});
			}
			pre=j;
		}
	}
	for(int i=1;i<=cnt;i++) dp[i]=INF;
	priority_queue< pair<long long,int>,vector< pair<long long,int> >,greater< pair<long long,int> > > pq;
	pq.push({dp[pos[1]]=0,pos[1]});
	while(!pq.empty())
	{
		long long a=pq.top().first,b=pq.top().second;
		pq.pop();
		if(dp[b]<a) continue;
		for(auto v:E[b]) if(dp[v.first]>a+v.second) pq.push({dp[v.first]=a+v.second,v.first});
	}
	if(dp[pos[n]]==INF) return cout<<-1,0;
	cout<<dp[pos[n]];
}

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