Submission #659034

#	Time	Username	Problem	Language	Result	Execution time	Memory
659034		rsjw	Robot (JOI21_ho_t4)	C++17	100 / 100	963 ms	120048 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
const int N = 500010;
#define int long long
namespace SSSP {
	struct edge {
		int to,w;
		edge *nex;
	}*head[N];
	void add(int u,int v,int w) {
//		printf("%d ----%d-----> %d\n",u,w,v);
		edge *cur=new edge;
		cur->to=v;
		cur->nex=head[u];
		cur->w=w;
		head[u]=cur;
	}
	int vis[N],dis[N];
	priority_queue<pair<int,int> > q;
	void dij(int s) {
		int u;
		memset(dis,0x3f,sizeof(dis));
		dis[s]=0;
		q.push(mp(-dis[s],s));
		while(!q.empty()) {
			u=q.top().second;
			q.pop();
			if(vis[u]) continue;
			vis[u]=1;
			for(edge *cur=head[u]; cur; cur=cur->nex) {
				if(dis[cur->to]>dis[u]+cur->w) {
					if(vis[cur->to]) printf("weird");
					dis[cur->to]=dis[u]+cur->w;
					q.push(mp(-dis[cur->to],cur->to));
				}
			}
		}
	}
} using namespace SSSP;
int cnt[N];
vector<tuple<int,int,int>> a[N];
int tot;
map<int,int> s[N];
signed main() {
	// freopen("1.in","r",stdin);
	int n,m,i,u,v,c,w;
	cin>>n>>m;
	tot=n;
	for(i=1; i<=m; i++) {
		cin>>u>>v>>c>>w;
		a[u].emplace_back(v,c,w);
		a[v].emplace_back(u,c,w);
		if(!s[u][c]) s[u][c]=++tot;
		if(!s[v][c]) s[v][c]=++tot;
	}
	for(u=1; u<=n; u++) {
		for(auto x:a[u]) {
			tie(v,c,w) = x;
			cnt[c]+=w;
		}
		for(auto x:a[u]) {
			tie(v,c,w) = x;
			add(u,v,min(w,cnt[c]-w));
			add(u,s[v][c],0);
			add(s[u][c],v,cnt[c]-w);
		}
		for(auto x:a[u]) {
			tie(v,c,w) = x;
			cnt[c]=0;
		}
	}
	dij(1);
	if(dis[n]==0x3f3f3f3f3f3f3f3f) dis[n]=-1;
	cout<<dis[n]<<endl;
	return 0;
}

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