自动搬运

查看原文

来自洛谷，原作者为

	ZnHF 这个留下很懒，什么也没有家伙

搬运于2025-08-24 22:06:41，当前版本为作者最后更新于2024-05-15 15:47:33，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意简述

给定一张有向图，求从点 $A$ 走到点 $B$ 的一条路径，这条路径满足：

1. 经过的边的权值总和是 $P$ 的倍数。
2. 在满足条件 $1$ 的情况下，经过的边的权值总和最小。

题目分析

本题可以使用分层图最短路来解决。

仿照动态规划的思想，定义 $f_{x,y}$ 表示从节点 $A$ 到达节点 $x$，经过的边的权值总和 $\bmod P$ 的值为 $y$ 时，经过的边的权值总和最小是多少。

然后进行一遍 Dijkstra 算法，设当前考虑的节点为 $a$，当前经过的边的权值总和 $\bmod P$ 的值为 $b$，扫描到一条通向点 $c$，权值为 $d$ 的边，在满足“当前位于点 $c$，经过的边的权值总和 $\bmod P$ 的值为 $(b+d) \bmod P$”这个状态没有被访问过的前提下，如果满足 $f_{c,(b+d) \bmod P} > f_{a,b}+d$，则使用 $f_{a,b}+d$ 更新 $f_{c,(b+d) \bmod P}$。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){register int t1=0,t2=0;register char x=getchar();while(x<'0' ||x>'9'){if(x=='-') t2|=1;x=getchar();}while(x>='0' && x<='9'){t1=(t1<<1)+(t1<<3)+(x^48),x=getchar();}return t2?-t1:t1;}
inline void write(int x){register int sta[35],top=0;if(x<0) putchar('-'),x=-x;do{sta[top++]=x%10,x/=10;}while(x);while(top) putchar(sta[--top]+48);}
int n,m,p,s,t,f[50005][55],pre_now[50005][55],pre_use[50005][55];
bool vis[50005][55];
struct edge{
	int to,l;
};
vector<edge> v[50005];
struct node{
	int now,sum,use;
};
priority_queue<node> q;
bool operator <(const node &a,const node &b){
	return a.sum>b.sum;
}
vector<int> ans;
void get(int x,int y){//通过保存的路径信息得到具体地路径 
	if(!x) return;
	ans.push_back(x);
	get(pre_now[x][y],pre_use[x][y]);
}
signed main(){
	n=read();
	m=read();
	p=read();
	s=read();
	t=read();
	for(int i=1;i<=m;i++){
		int t1=read(),t2=read(),t3=read();
		v[t1].push_back({t2,t3});
	}
	memset(f,0x3f,sizeof(f));
	f[s][0]=0;
	q.push({s,0,0});
	while(!q.empty()){
		node temp=q.top();
		q.pop();
		if(vis[temp.now][temp.use]) continue;
		vis[temp.now][temp.use]=1;
		for(int i=0;i<v[temp.now].size();i++){
			int t1=v[temp.now][i].to,t2=v[temp.now][i].l;
			if(!vis[t1][(temp.use+t2)%p] && f[t1][(temp.use+t2)%p]>f[temp.now][temp.use]+t2){
				f[t1][(temp.use+t2)%p]=f[temp.now][temp.use]+t2;
				pre_now[t1][(temp.use+t2)%p]=temp.now;//保存路径信息 
				pre_use[t1][(temp.use+t2)%p]=temp.use;//同上 
				q.push({t1,f[t1][(temp.use+t2)%p],(temp.use+t2)%p});
			}
		}
	}
	if(f[t][0]==4557430888798830399) puts("jjc fails in travelling");//考虑无法完成的情况
	else{
		write(f[t][0]);
		putchar('\n');
		get(t,0);
		for(int i=ans.size()-1;i>0;i--){
			write(ans[i]);
			putchar('-');
			putchar('>');
		}
		write(ans[0]);
	}
	return 0;
}