自动搬运

查看原文

来自洛谷，原作者为

	xpsroc **

搬运于2025-08-24 22:52:04，当前版本为作者最后更新于2023-10-27 20:35:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

一眼看此题有两个边权好像很复杂。

再看数据范围，直接分层图也炸不了。

按照第二个边权的值分层图，这样按照数据最多分二百层的图。

只需要每次建边时把每层图的起点与加上第二个边权的另一层图的终点建边就好了（当然不要忘记建本题为无向图）。

最后跑一遍 Dijkstra 就可以了。

接下来放代码。

Code

#include<iostream>
#include<cstdio>
#include<functional>
#include<queue>
using namespace std;
#define int long long
const int N=2050;
int k,n,m,s,t;
typedef pair<int,int >pr;
priority_queue<pr, vector<pr >, greater<pr> >q;
int h[N*205],d[N*205],vis[N*205];//写分层图别忘了数组范围 
struct ed{
	int ne,to,sum;
}a[40100000];
int cnt=0;
void add(int u,int v,int w){
	a[++cnt].ne=h[u];a[cnt].to=v;a[cnt].sum=w;
	h[u]=cnt;
}
const int Inf=0x7f7f7f7f;
signed main(){
	cin>>k>>n>>m;
	for(int i=1; i<=m; i++){
		int ax,bx,cx,dx;cin>>ax>>bx>>cx>>dx;
		for(int j=0; j<=k; j++){
			add(ax+j*n,bx+j*n+dx*n,cx);//分层图核心思想 
			add(bx+j*n,ax+j*n+dx*n,cx);//建两条边 
		}
	}
	cin>>s>>t;
	//Dijkstra 
	for(int i=1; i<=n*204; i++)d[i]=Inf;
	q.push(make_pair(0,s));d[s]=0;
	while(!q.empty()){
		pr it=q.top();q.pop();
		int kkx=it.first,u=it.second;
		if(vis[u]==1)continue;
		vis[u]=1;
		for(int i=h[u]; i!=0; i=a[i].ne){
			int v=a[i].to;
			if(d[v]>d[u]+a[i].sum){
				d[v]=d[u]+a[i].sum;
				q.push(make_pair(d[v],v));
			}
		}
	}
	int anss=Inf;
	for(int i=0; i<k; i++){
		if(d[t+i*n]!=Inf)anss=min(anss,d[t+i*n]);
	}//判断只需要前k层中有一层的终点能到达就行了。 
	if(anss==Inf)cout<<-1<<endl;
	else cout<<anss<<endl;
}