列表

详情

NC20970. [NOI2018]归程

描述

本题的故事发生在魔力之都，在这里我们将为你介绍一些必要的设定。

魔力之都可以抽象成一个个节点、条边的无向连通图（节点的编号从至）。我们依次用描述一条边的长度、海拔。

作为季风气候的代表城市，魔力之都时常有雨水相伴，因此道路积水总是不可避免的。由于整个城市的排水系统连通，因此有积水的边一定是海拔相对最低的一些边。

我们用水位线来描述降雨的程度，它的意义是：所有海拔不超过水位线的边都是有积水的。

Yazid 是一名来自魔力之都的 OIer，刚参加完 ION2018 的他将踏上归程，回到他温暖的家。

Yazid 的家恰好在魔力之都的号节点。对于接下来天，每一天 Yazid 都会告诉你他的出发点，以及当天的水位线。

每一天，Yazid 在出发点都拥有一辆车。这辆车由于一些故障不能经过有积水的边。

Yazid 可以在任意节点下车，这样接下来他就可以步行经过有积水的边。但车会被留在他下车的节点并不会再被使用。

Yazid 非常讨厌在雨天步行，因此他希望在完成回家这一目标的同时，最小化他步行经过的边的总长度。请你帮助 Yazid 进行计算。

本题的部分测试点将强制在线，具体细节请见「输入格式」和「子任务」。


输入描述

单个测试点中包含多组数据。
输入的第一行为一个非负整数 T，表示数据的组数。
接下来依次描述每组数据，对于每组数据：
• 第一行 2 个非负整数 n, m，分别表示节点数、边数。
• 接下来 m 行，每行 4 个正整数 u, v, l, a，描述一条连接节点 u, v 的、长度为 l、海
拔为 a 的边。
– 在这里，我们保证 1 ≤ u, v ≤ n。
• 接下来一行 3 个非负数 Q, K, S，其中 Q 表示总天数，K ∈ {0, 1} 是一个会在下面
被用到的系数，S 表示的是可能的最高水位线。
• 接下来 Q 行依次描述每天的状况。每行 2 个整数 v0, p0 描述一天：
– 这一天的出发节点为 v = (v0 + K × lastans − 1) mod n + 1。
– 这一天的水位线为 p = (p0 + K × lastans) mod (S + 1)。
– 其中 lastans 表示上一天的答案（最小步行总路程）。特别地，我们规定第 1
天时 lastans = 0。
– 在这里，我们保证 1 ≤ v0 ≤ n，0 ≤ p0 ≤ S。
对于输入中的每一行，如果该行包含多个数，则用单个空格将它们隔开

输出描述

依次输出各组数据的答案。对于每组数据：
输出 Q 行每行一个整数，依次表示每天的最小步行总路程。

示例1

输入: 

1
4 3
1 2 50 1
2 3 100 2
3 4 50 1
5 0 2
3 0
2 1
4 1
3 1
3 2

输出: 

0
50
200
50
150

说明:

第一天没有降水，Yazid 可以坐车直接回到家中。
第二天、第三天、第四天的积水情况相同，均为连接 1, 2 号节点的边、连接 3, 4 号
点的边有积水。
对于第二天，Yazid 从 2 号点出发坐车只能去往 3 号节点，对回家没有帮助。因此
Yazid 只能纯靠徒步回家。
对于第三天，从 4 号节点出发的唯一一条边是有积水的，车也就变得无用了。Yazid
只能纯靠徒步回家。
对于第四天，Yazid 可以坐车先到达 2 号节点，再步行回家。
第五天所有的边都积水了，因此 Yazid 只能纯靠徒步回家。

示例2

输入: 

1
5 5
1 2 1 2
2 3 1 2
4 3 1 2
5 3 1 2
1 5 2 1
4 1 3
5 1
5 2
2 0
4 0

输出: 

0
2
3
1

说明:

本组数据强制在线。
第一天的答案是 0，因此第二天的 v = (5 + 0 − 1) mod 5 + 1 = 5，p = (2 + 0) mod
(3 + 1) = 2。
第二天的答案是 2，因此第三天的 v = (2 + 2 − 1) mod 5 + 1 = 4，p = (0 + 2) mod
(3 + 1) = 2。
第三天的答案是 3，因此第四天的 v = (4 + 3 − 1) mod 5 + 1 = 2，p = (0 + 3) mod
(3 + 1) = 3。

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 1961ms, 内存消耗: 117360K, 提交时间: 2023-07-21 04:05:51 

#include<bits/stdc++.h>
#define mid (l+r>>1)
#define rgi register int
typedef long long ll;
using namespace std;
inline void read(){}template <typename T,typename... Ts> inline void read(T& A,Ts&... As){
	T x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	A=x*f,read(As...);
}
inline void write(char a){putchar(a);}
template <typename T> inline void write(T a){
	if(a<0ll)putchar('-'),a=-a;
	if(a>9ll)write(a/10ll);
	putchar(a%10ll+'0');
}
template <typename T,typename... Ts> inline void write(T A,Ts... As){write(A),write(As...);}
const int N=200010,M=500010,inf=(1<<30);
int n,m,q;


// 并查集 
int fa[N<<1];
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}

//kruskal重构树 
struct E{
	int st,to,val;
	bool operator<(E x)const{
		return val>x.val;
	}
}e[M];
vector<int>a[N<<1];
int tot;
inline void link(int u,int v){
	a[u].push_back(v),a[v].push_back(u);
}

//最短路 
int dis[N<<1];
struct node{
	int id,dis;
	bool operator<(node k)const{
		return dis>k.dis;
	}
};
struct edge{int to,val;};
int vis[N];
priority_queue<node>Q;
vector<edge>g[N<<1];
void dij(int n,int m,int s){
	for(rgi i=1;i<=n;i++)dis[i]=1147483647,vis[i]=0;
	dis[s]=0;
	Q.push(node{s,0});
	while(!Q.empty()){
		int x=Q.top().id;
		Q.pop();
		if(vis[x])continue;
		vis[x]=1;
		for(rgi i=0;i<g[x].size();++i){
			int to=g[x][i].to;
			int val=g[x][i].val;
			if(dis[to]>dis[x]+val){
				dis[to]=dis[x]+val;
				Q.push(node{to,dis[to]});
			}
		}
	}
}

//倍增 
int p[N<<1][21],seq[N],in[N<<1],out[N<<1],C;
void dfs(int x,int f){
	p[x][0]=f;
	if(x<=n)seq[++C]=dis[x];
	in[x]=C;
	for(rgi i=0;i<a[x].size();++i){
		int to=a[x][i];
		if(to!=f)dfs(to,x);
	}
	out[x]=C;
}

//st表 
int mi[N][21];
int qry(int l,int r){
    int k=log2(r-l+1); 
    return min(mi[l][k],mi[r-(1<<k)+1][k]);
}

int las,op,S;
signed main(){
	int T;
	read(T);
	while(T--){
		read(n,m),tot=n,C=0;
		for(rgi i=1;i<=(n<<1);++i){
			fa[i]=i,g[i].clear(),a[i].clear();
		}
		memset(p,0,sizeof p),memset(mi,0,sizeof mi);
		for(rgi i=1;i<=m;++i){
			int w;
			read(e[i].st,e[i].to,w,e[i].val);
			g[e[i].st].push_back(edge{e[i].to,w});
			g[e[i].to].push_back(edge{e[i].st,w});
		}
		dij(n,m,1),dis[n+1]=0;
		sort(e+1,e+m+1);
		for(rgi i=1;i<=m;++i){
			int fx=find(e[i].st),fy=find(e[i].to);
			if(fx!=fy){
				fa[fx]=fa[fy]=++tot;
				link(fx,tot),link(fy,tot);
				dis[tot]=e[i].val,fa[tot]=tot;
			}
		}
		dfs(tot,0);
		for(rgi i=1;i<=n;++i)mi[i][0]=seq[i];
		for(rgi w=1;w<20;++w){
			for(rgi i=1;i<=tot;++i)p[i][w]=p[p[i][w-1]][w-1];
			for(rgi i=1;i+(1ll<<(w-1))<=n;++i)mi[i][w]=min(mi[i][w-1],mi[i+(1<<(w-1))][w-1]);
		}
		read(q,op,S),las=0;
		while(q--){
			int x,u;
			read(u,x);
			u=(u+op*las-1)%n+1;
			x=(x+op*las)%(S+1);
			for(rgi i=19;~i;--i){
				if(p[u][i]&&dis[p[u][i]]>x)u=p[u][i];
			}
			write(las=(u<=n?dis[u]:qry(in[u]+1,out[u])),'\n');
		}
	}
	return 0;
}
/*
2
4 3
1 2 50 1
2 3 100 2
3 4 50 1
5 0 2
3 0
2 1
4 1
3 1
3 2
4 3
1 2 50 1
2 3 100 2
3 4 50 1
5 0 2
3 0
2 1
4 1
3 1
3 2

*/

C++14(g++5.4) 解法, 执行用时: 2362ms, 内存消耗: 93048K, 提交时间: 2020-09-21 08:40:15 

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout)
#define mp make_pair
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=400000+10;

int n,m;

struct edge { int u,v,l,a; } e[N];
bool operator <(edge a,edge b) { return a.a>b.a; }
vector<pair<int,int> > E[N];
vector<int> T[N];

struct node { int u,d; };
bool operator <(node a,node b) { return a.d>b.d; }
int dis[N];
void dijkstra() {
    priority_queue<node> Q; Q.push((node){1,0});
    memset(dis,0x3f,sizeof(dis)); dis[1]=0;
    while (!Q.empty()) {
        int u=Q.top().u,d=Q.top().d; Q.pop();
        if (d!=dis[u]) continue;
        for (auto t:E[u]) { int v=t.first,w=t.second;
            if (d+w<dis[v]) Q.push((node){v,dis[v]=d+w});
        }
    }
}

struct dsu {
    int f[N];
    int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }
} U;

int f[19][N],height[N],mindis[N];
void dfs(int u,int fa) {
    f[0][u]=fa;
    for (int i=1;i<=18;++i) f[i][u]=f[i-1][f[i-1][u]];
    for (int v:T[u]) dfs(v,u),mindis[u]=min(mindis[u],mindis[v]);
}
int jump(int u,int lim) {
    for (int i=18;~i;--i)
        if (height[f[i][u]]>lim) u=f[i][u];
    return u;
}
void build() {
    sort(e+1,e+m+1); int tot=n;
    for (int i=1;i<n<<1;++i) U.f[i]=i,T[i].clear();
    for (int i=1;i<=m;++i) {
        int u=e[i].u,v=e[i].v;
        if (U.find(u)!=U.find(v)) {
            height[++tot]=e[i].a;
            T[tot].emplace_back(U.find(u)),U.f[U.find(u)]=tot;
            T[tot].emplace_back(U.find(v)),U.f[U.find(v)]=tot;
        }
    }
    for (int i=1;i<=n;++i) mindis[i]=dis[i];
    for (int i=n+1;i<=tot;++i) mindis[i]=2e9;
    dfs(tot,0);
}

int main() {
    int T=read();
    while (T--) {
        n=read(),m=read();
        for (int i=1;i<=n;++i) E[i].clear();
        for (int i=1;i<=m;++i) {
            int u=read(),v=read(),l=read(),a=read();
            e[i]=(edge){u,v,l,a};
            E[u].emplace_back(mp(v,l));
            E[v].emplace_back(mp(u,l));
        }
        dijkstra(); build();
        int Q=read(),K=read(),S=read();
        int lastans=0;
        while (Q--) {
            int v=(read()+K*lastans-1)%n+1;
            int p=(read()+K*lastans)%(S+1);
            printf("%d\n",lastans=mindis[jump(v,p)]);
        }
    }
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 1161ms, 内存消耗: 63144K, 提交时间: 2022-09-05 13:19:28 

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue> 
using namespace std;
const int M = 400005;
int read()
{
    int num=0,flag=1;char c;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;
    while(c>='0'&&c<='9')num=(num<<3)+(num<<1)+(c^48),c=getchar();
    return num*flag;
}
int T,n,m,tot,cnt,f[M],dis[M],fa[M],a[M],ans[M],p[M][20];
struct edge
{
	int v,c,next;
}e[2*M];
struct edge2
{
	int u,v,l,a;
	bool operator < (const edge2 &b) const
	{
		return a>b.a;
	}
}s[M];
struct node
{
	int u,c;
	bool operator < (const node &b) const
	{
		return c>b.c;
	}
};
void dijk()
{
	priority_queue<node> q;
	memset(dis,0x3f,sizeof dis);
	dis[1]=0;q.push(node{1,0});
	while(!q.empty())
	{
		node t=q.top();q.pop();
		if(dis[t.u]<t.c) continue;
		for(int i=f[t.u];i;i=e[i].next)
		{
			int v=e[i].v,c=e[i].c;
			if(dis[v]>dis[t.u]+c)
			{
				dis[v]=dis[t.u]+c;
				q.push(node{v,dis[v]});
			}
		}
	}
}
int find(int x)
{
	if(x!=fa[x]) fa[x]=find(fa[x]);
	return fa[x];
}
void add(int u,int v,int c)
{
	e[++tot]=edge{v,c,f[u]},f[u]=tot;
}
void dfs(int u,int fa)
{
	p[u][0]=fa;
	for(int i=1;i<20;i++)
		p[u][i]=p[p[u][i-1]][i-1];
	for(int i=f[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if(v==fa) continue;
		dfs(v,u);
		dis[u]=min(dis[u],dis[v]);
	}
}
void kruskal()
{
	cnt=n;
	for(int i=1;i<=2*n;i++)
		fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		int u=s[i].u,v=s[i].v,t=s[i].a;
		int x=find(u),y=find(v);
		if(x!=y)
		{
			add(++cnt,x,0);add(cnt,y,0);
			fa[y]=fa[x]=cnt;a[cnt]=t;
		}
	}
	dfs(cnt,0);
}
signed main()
{
	T=read();
	while(T--)
	{
		memset(a,0,sizeof a);
		memset(f,0,sizeof f);tot=0;
		n=read();m=read();
		for(int i=1;i<=m;i++)
		{
			int u=read(),v=read(),l=read(),a=read();
			add(u,v,l);add(v,u,l);
			s[i]=edge2{u,v,l,a};
		}
		dijk();
		sort(s+1,s+1+m);
		memset(f,0,sizeof f);tot=0;
		kruskal();
		int q=read(),k=read(),S=read(),ans=0;
		while(q--)
		{
			int v=read(),pw=read();
			v=(v+k*ans-1)%n+1;
			pw=(pw+k*ans)%(S+1);
			for(int i=19;i>=0;i--)
				if(a[p[v][i]]>pw)
					v=p[v][i];
			printf("%d\n",ans=dis[v]);
		}
	}
}

上一题

© 2024 nowcoder.com