P10178 陌路寻诗礼
题目背景
作为 luogu 网红的帆巨，有非常多狂热的粉丝，而我们的帆巨也很喜欢面基，寻找遍布大江南北的粉丝们。
题目描述
帆巨所在的家乡的地图是一张有nnn个节点mmm条有向道路的有向图，每个节点都是一个城市，而帆巨所在的城市是111号城市，并且111号城市总是可以通过若干道路到达其他任何城市。
第iii条道路从xix_ixi号城市出发到达yiy_iyi号城市，长度为ziz_izi。
帆帆现在要从他的111号城市前往各个城市面基。
精通 spfa 算法的帆帆在面基的过程中自然会按照长度和最短的路径去其他城市。
但是帆帆有选择困难症，他希望从111号城市到达每一座城市的最短路径都是唯一的，所以他决定施加魔法，改变所有道路的长度，具体地：
帆巨施加魔法后，对于每一条道路的长度，都可以独立地将其变成一个[1,k][1,k][1,k]范围内的整数，其中kkk是帆巨的魔法等级。
但帆巨所在的世界的地图和他的魔法等级一直在变，总共会变TTT次，所以他希望你对TTT次询问都给出一种构造方法使得帆巨不会纠结或者报告无解。
输入格式
第一行一个整数TTT表示数据组数。
接下来TTT组，每组先是三个整数n,m,kn,m,kn,m,k，接着mmm行描述有向道路(xi,yi)(x_i,y_i)(xi,yi)。
不保证无自环无重边。
输出格式
对于每组数据，如果有解，第一行输出Yes，第二行mmm个数依次输出每条边的权值；如果没有解，一行输出No。
本题采用special judge评测，也就是说，如果有多种可能的答案，你可以输出任意一种。
输入输出样例 #1
输入 #1
2 3 2 3 1 2 2 3 2 2 1 1 2 1 2输出 #1
Yes 1 2 No说明/提示
【样例解释】
对于第一组数据，111号点到达每个点的路径都是唯一，自然无论怎么设置边权，最短路都是唯一的。
对于第二组数据，因为k=1k=1k=1，所以两条边的边权都只能设置为111。111号点到222号点的最短路长度为111，走两条边都可以，所以不是唯一的。
【数据范围】
本题采用捆绑测试。
对于20%20\%20%的数据，n,m≤5n,m\leq 5n,m≤5。
对于另外20%20\%20%的数据，k=1k=1k=1。
对于另外20%20\%20%的数据，m=n−1m=n-1m=n−1。
对于另外20%20\%20%的数据，k=109k=10^9k=109。
对于100%100\%100%的数据，n≥1n\ge 1n≥1，m≥0m\ge 0m≥0，1≤∑n,∑m≤3×1051\le \sum n,\sum m\leq 3\times 10^51≤∑n,∑m≤3×105，1≤k≤1091\leq k \leq 10^91≤k≤109，1≤xi,yi≤n1\le x_i,y_i\le n1≤xi,yi≤n。
C++实现
#include<bits/stdc++.h>usingnamespacestd;constintN=3e5+10;intT,n,m,k,d[N];vector<pair<int,int>>g[N];boolvis[N],tf;queue<int>q;intmain(){scanf("%d",&T);while(T--){scanf("%d%d%d",&n,&m,&k);tf=false;for(inti=1;i<=n;++i)d[i]=-1,g[i].clear();for(inti=1,x,y;i<=m;++i){scanf("%d%d",&x,&y);vis[i]=false;g[x].push_back(make_pair(y,i));}d[1]=0;q.push(1);while(!q.empty()){intx=q.front();q.pop();for(autotmp:g[x]){inty=tmp.first;if(d[y]!=-1){if(d[y]==d[x]+1)tf=true;continue;}d[y]=d[x]+1;vis[tmp.second]=true;q.push(y);}}if(k==1&&tf){puts("No");continue;}puts("Yes");for(inti=1;i<=m;++i)if(vis[i])cout<<1<<" \n"[i==m];elsecout<<k<<" \n"[i==m];}return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
