自动搬运

查看原文

来自洛谷，原作者为

	CleverRaccoon 不蓝钩不改个签

搬运于2025-08-24 22:55:27，当前版本为作者最后更新于2024-02-24 18:06:51，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前言

我认为官方题解的思路和代码稍有些复杂，所以来分享一下我的思路。

代码似乎和 dijkstra 板子没差几行。

题目描述

在一个 $n$ 个点 $m$ 条边的无向图中构造出每条边的长度 $z_i$（$1\leq z_i\leq k$），使得点 $1$ 到任何一个点的最短路径都是唯一的，如果不能做到，则报告无解。

思路

考场上我的做法只涉及到了普通的 dijkstra 进行略微的修改。

文中提到的 spfa 算法很好地帮助我们很好的想到了 dijkstra 算法（spfa 算法可能会被卡，而且也没有负权，因为 $1\leq z_i\leq k$）。

• 首先写好 dijkstra 的板子。

• 接下来，我们思考，如果所有最短路径都是唯一的，那么每条边的边权 $z_i=1$ 即可。

• 如果有最短路径不唯一呢？如果找到一条路径和当前找到的路径长度相同，那么如果当前找到了第 $i$ 条边，使 $z_i\to z_i+1$ 即可，这样就可以避免路径长度相同了。

• 接下来，判定无解：如何判定无解呢？因为我们只要在第 $i$ 条边找到一条长度相同的最短路径，就会使 $z_i\to z_i+1$，那么很有可能 $z_i$ 经过多次 $z_i\to z_i+1$ 就会超过 $k$，超过 $k$ 即无解。故只要判断 $z_i$ 中的最大值是否大于 $k$ 即可。如果大于 $k$ 则无解；否则有解，输出每条边的边权 $z$ 数组即可。

一句话总结，先写 dijkstra 板子，然后边权全部初始化为 $1$，如果碰上路径长度相同，则将当前这条边的边权加一，最后判断如果最大边权超过 $k$，则无解，否则有解，输出答案即可。

个人认为自己的思路比较简单易想且写起来很方便。

代码

相比 dijkstra 模板，基本上没改几行。

#include <bits/stdc++.h>
using namespace std;

const int INF=1e9;
const int N=3e5+5;

struct nodee{
	int to,id;	// id 记录是第几条边
};

vector<nodee> e[N];
int n,m,k;
int T;
bool vis[N];
int dis[N];
int ans[N],mx;	// ans 数组即 z 数组，mx 记录 ans 的最大值，以便判断是否大于 k

struct node{
	int id,val;
	bool operator<(const node &o)const{	// 比较结构体大小
		return val>o.val;
	}
};

bool dijkstra(int s){	// dijkstra 板子
	memset(vis,0,sizeof vis);	// 清空很重要
	memset(dis,0x3f,sizeof dis);
	mx=-INF;	// 求最大，所以先设为一个极小值
	priority_queue<node> q;	// 使用优先队列优化
	q.push({s,0});
	dis[s]=0;
	while(!q.empty()){
		int u=q.top().id;
		int val=q.top().val;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(int i=0;i<e[u].size();i++){
			int v=e[u][i].to,id=e[u][i].id;
			if(dis[v]>dis[u]+1){	// 边权都是 1，由于每条边只会遍历一次，所以修改不会影响唯一一次遍历时的边权 1
				dis[v]=dis[u]+1;
				q.push({v,dis[v]});
			}else if(dis[v]==dis[u]+1){	// 如果最短路径长度相同，那么 ++ans[id] 同时记录最大值即可
				mx=max(mx,++ans[id]);
			}
		}
	}
	return mx<=k;	// 如果最大值不超过 k 那么就有解
}

int main(){
	cin>>T;
	while(T--){
		cin>>n>>m>>k;
		for(int i=1;i<=n;i++)e[i].clear();	// 清空
		for(int i=1;i<=m;i++){
			int x,y;
			cin>>x>>y;
			e[x].push_back({y,i});	// 要记录是第 i 条边
		}
		fill(ans+1,ans+m+1,1);	// 一开始边权 ans 即 z 都设为 1
		if(dijkstra(1)){	// 有解
			puts("Yes");
			for(int i=1;i<=m;i++)cout<<ans[i]<<" \n"[i==m];	// 输出答案即可
		}else puts("No");
	}
	return 0;
}

然后就能通过本题了。