题解：P11860 [CCC 2025 Senior] 熔岩路 / Floor is Lava

总花费是答案路径上所有相邻边的权值之差，所以由此可以推出部分分的做法：把原图中所有边当做点建一个新图，连接共点边作为新边，权值为原图中边权之差。建一个超级源点和一个超级汇点，跑最短路即可。

优化比较明确：在一个点上改变自身权值多次，只要始末态不变，花费就不变，所以只需要给原图中的点的连边按照边权排序，给排位相邻的边建新边即可，其它的边可以通过这些边中转，结果不变。

记得把初始值开大一点哦～

CPP

const ll N=2e5+10;
ll n,m;
vector<pll> g[N],gg[N];

void input() {
//	freopen("P11860_2.in.txt","r",stdin);
	cin>>n>>m;

	rep(i,1,m) {
		ll u,v,w;
		cin>>u>>v>>w;
		g[u].pb({w,i});
		g[v].pb({w,i});
	}
}

void instruct() {
	rep(i,2,n-1) {
		sort(g[i].begin(),g[i].end());

		rep(j,1,g[i].size()-1) {
			ll u=g[i][j].se,v=g[i][j-1].se,w=abs(g[i][j].fi-g[i][j-1].fi);
			gg[u].pb({v,w});
			gg[v].pb({u,w});
		}
	}

	for(pll i:g[1]) {
		ll u=0,v=i.se,w=i.fi;
		gg[u].pb({v,w});
		gg[v].pb({u,w});
	}
	
	for(pll i:g[n]) {
		ll u=m+1,v=i.se,w=0;
		gg[u].pb({v,w});
		gg[v].pb({u,w});
	}
	
//	rep(i,0,m+1){
//		cout<<"i="<<i<<":";
//		
//		for(pll j:gg[i]) cout<<j.fi<<' ';
//		
//		endl;
//	}
//	
//	pause;
}

const ll inf=922337203685477580;
ll ans[N];
bool vis[N];
pqueue(pll,greater) pq;

void dij(){
	rep(i,1,m+1) ans[i]=inf;
	
	pq.push({0,0});
	
	while(pq.empty()==0){
		pll cur;
		xtop(cur,pq);
		
		if(vis[cur.se]) ctn;
		else vis[cur.se]=1;
		
		for(pll i:gg[cur.se]) {
//			update(ans[i.fi],cur.fi+i.se,min);
			
			if(cur.fi+i.se<ans[i.fi]){
				ans[i.fi]=cur.fi+i.se;
				pq.push({ans[i.fi],i.fi});
			}
		}
	}
	
//	cout<<"ans[]:";
//	
//	rep(i,0,m+1) cout<<ans[i]<<' ';
//	
//	endl;
//	pause;
}

void output(){
	cout<<ans[m+1];
}

int main() {
	input();
	instruct();
	dij();
	output();
}

题解：P11860 [CCC 2025 Senior] 熔岩路 / Floor is Lava

文章操作

相关推荐

评论

题解：P11860 [CCC 2025 Senior] 熔岩路 / Floor is Lava