首页 > 其他分享 >[USACO21DEC] Tickets P 题解

[USACO21DEC] Tickets P 题解

时间:2024-11-06 17:43:03浏览次数:2  
标签:Tickets int 题解 void tn MAXN text USACO21DEC dis

[USACO21DEC] Tickets P

首先我们思考暴力的 \(O(n^2)\) 怎么做。显然比起每次以 \(i\) 为起点跑 \(n\) 遍最短路,建反图后分别以 \(1\) 和 \(n\) 为起点跑两遍最短路是更加经济的方式。然后你可能会以为 \(\text{dis}(1,i)+\text{dis}(n,i)\) 就是答案了,之后你就会发现连样例都过不去。

为什么呢?假如说 \(n=4\),\(i=3\),此时 \(\text{path}(1,3)=1\to2\to3\),而 \(\text{path}(3,4)=3\to2\to4\),那么 \((2,3)\) 这条边就算重了。

如何解决?方法是将 \((\forall i)~\text{dis}(1,i)+\text{dis}(n,i)\) 作为每个点的初始 \(\text{dis}\),然后再跑一遍最短路,此时得到的 \(\text{dis}_i\) 就是每个点的答案了。然后你又会发现一个问题,就是某些点它转移不到。所以建边的时候一定是先把当前点和一个虚点连一条有花费的边,再把虚点和区间上的所有点连边权为 0 的边。这样跑出来的就是正确的。

37pts 就有了。

怎么优化到 100pts?线段树优化建图即可。

#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
#define INF 0x3f3f3f3f3f3f3f3fll
using namespace std;

char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
	int x=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}
template<typename T>
void write(T x,char sf='\n'){
	if(x<0)putchar('-'),x=~x+1;
	int top=0;
	do str[top++]=x%10,x/=10;while(x);
	while(top)putchar(str[--top]+48);
	if(sf^'#')putchar(sf);
}
using ll=long long;
using pli=pair<ll,int>;
constexpr int MAXN=4e5+5;
int n,k,tn;
struct Tik{
	int c,p,a,b;
}t[MAXN];
int head[MAXN],tot;
struct{
	int v,to,w;
}e[5000005];
void addedge(int u,int v,int w){
	e[++tot]={v,head[u],w};
	head[u]=tot;
}
ll dis[MAXN],d[MAXN];
bool vis[MAXN];
priority_queue<pli>q;
void dijkstra(int s,bool sh=0){
	memset(vis,0,sizeof(bool)*(tn+k+5));
	if(!sh){
		memset(dis,0x3f,sizeof(ll)*(tn+k+5));
		dis[s]=0;
		q.emplace(0,s);
	}else{
		memcpy(dis,d,sizeof(ll)*(tn+k+5));
		for(int i=1;i<=tn+k;++i)
			q.emplace(-dis[i],i);
	}
	while(!q.empty()){
		int u=q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=head[u];i;i=e[i].to)
			if(dis[e[i].v]>dis[u]+e[i].w){
				dis[e[i].v]=dis[u]+e[i].w;
				q.emplace(-dis[e[i].v],e[i].v);
			}
	}
}

#define lp p<<1
#define rp p<<1|1
struct{
	struct SegTree{
		int l,r,ls,rs;
	}st[MAXN];
	int build(int s,int t){
		if(s==t) return st[s]={s,t,0,0},s;
		int mid=(s+t)>>1,x=++tn;
		st[x]={s,t,build(s,mid),build(mid+1,t)};
		addedge(st[x].ls,x,0);
		addedge(st[x].rs,x,0);
		return x;
	}
	void update(int l,int r,int x,int p){
		if(l<=st[p].l&&st[p].r<=r) return addedge(p,x,0);
		int mid=(st[p].l+st[p].r)>>1;
		if(l<=mid) update(l,r,x,st[p].ls);
		if(mid<r) update(l,r,x,st[p].rs);
	}
}T;

int main(){
	n=tn=read(),k=read();
	int rt=T.build(1,n);
	for(int i=1;i<=k;++i){
		t[i]={read(),read(),read(),read()};
		addedge(tn+i,t[i].c,t[i].p);
		T.update(t[i].a,t[i].b,tn+i,rt);
	}
	dijkstra(1);
	memcpy(d,dis,sizeof(ll)*(tn+k+5));
	dijkstra(n);
	for(int i=1;i<=tn+k;++i) d[i]+=dis[i];
	dijkstra(1,1);
	for(int i=1;i<=n;++i) write(d[i]>=INF?-1:dis[i]);
	return fw,0;
}

标签:Tickets,int,题解,void,tn,MAXN,text,USACO21DEC,dis
From: https://www.cnblogs.com/laoshan-plus/p/18530663

相关文章

  • 【问题解决】java.lang.SecurityException: JCE cannot authenticate the provider BC
    问题复现历史项目升级JDK(由1.7升级到8),进行加密/解密时出现报错java.lang.SecurityException:JCEcannotauthenticatetheproviderBC。问题原因Wikipa上查到JCE的描述如下:JavaCryptographyExtension(JCE)isanofficiallyreleasedStandardExtensiontotheJavaPl......
  • 【问题解决】Tomcat由低于8版本升级到高版本使用Tomcat自带连接池报错无法找到表空间
    问题复现项目上历史项目为解决漏洞扫描从Tomcat6.0升级到了9.0版本,服务启动的日志显示如下警告,数据源是通过JNDI方式在server.xml中配置的,控制台上狂刷无法找到表空间的错误(没截图)报错:06-Nov-202410:32:03.701警告[main]java.util.ArrayList.forEachName=数据源Proper......
  • CF1909题解
    CF1909A一眼秒之题,我们发现就是四个方向选三个方向,若是存在一个点它的方向恰好在(0,0)点的另外一个方向,则一定不成立枚举4个方向,发现有点在这个方向,显然选除这个点之外的三个方向的方案就不可行点击查看代码#include<bits/stdc++.h>usingnamespacestd;constintN=105;int......
  • 题解:P7082 [NWRRC2013] Dwarf Tower
    涉及知识点:动态规划。解题思路设\(dp_i\)为得到\(i\)最小的花费。可以得到转移方程:\(dp_{a_i}=\min(dp_{x_i}+dp_{y_i},dp_{a_i})\)。很明显最多迭代\(n\)次,还需要再外面套一个循化即可。但是有些OJ没有洛谷跑得快,所以需要加一点优化。如果当前循环没有更新......
  • 【题解】CF1956
    CF1956A简要题意有\(n\)个人玩一个游戏,把这\(n\)个人分别编号为\(1\)到\(n\)。每一轮,编号为\(a_1,a_2,\ldots,a_k\)(\(a\)序列递增)的人会被踢出这个游戏,剩下的人会补齐空位并重新从\(1\)开始编号。当某一轮没有人被踢出时,游戏结束,剩下没有被踢出的人成为......
  • “SSL 证书验证失败”问题解决方法“urllib.error.URLError: <urlopen error [SSL: CER
    第一部分:问题描述第二部分:解决方法错误的代码:dataset_train=datasets.MNIST('../data/mnist/',train=True,download=True,transform=trans_mnist)dataset_test=datasets.MNIST('../data/mnist/',train=False,download=True,transform=trans......
  • P6667 [清华集训2016] 如何优雅地求和 题解
    一道非常有启发性的题目。思路考虑对于一个给出点值的多项式函数如何处理。我们发现,对于一个\(m\)次多项式\(f(x)\),由于\(\binom{x}{i}\)为\(i\)次多项式,所以说我们必定可以把一个多项式函数写成如下模样:\[F(k)=\sum_{i=0}^m\binom{k}{i}f_i\]可以看出,\(f_i\)实际上......
  • CSP-J2024题解
    T1扑克牌本题要求:在给定的扑克牌的基础上,还需要多少张牌可以让扑克牌凑成一整套,试题中读入的字符串每个都代表一张合法的扑克牌。可以使用C++STL中的set(集合)完成本题。这是因为,set可以自动去重,去除重复的牌(字符串)后,剩下的字符串就是实际拥有的不同的牌。而一副扑克牌有......
  • ABC378 E 题解
    ABC378E题解题意给定序列\(A\),求\(\sum_{1\lel\ler\len}(\sum_{l\lei\ler}A_i\modM)\)计算所有区间和取模之后的结果再求和。注意外层是没有取模的。如果是外层也要取模的情况,那还是十分好办的,直接贡献法计算每个数字被统计了多少次就可以了。问题就在于外层没......
  • 2024强网杯web题解
    PyBlocklyfromflaskimportFlask,request,jsonifyimportreimportunidecodeimportstringimportastimportsysimportosimportsubprocessimportimportlib.utilimportjsonapp=Flask(__name__)app.config['JSON_AS_ASCII']=Falseblacklis......