打卡信奥刷题（3421）用C++实现信奥题 P10178 陌路寻诗礼

📅 2026/7/2 10:56:22 👁️ 次浏览

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输入 #12 3 2 3 1 2 2 3 2 2 1 1 2 1 2输出 #1Yes 1 2 No说明/提示【样例解释】对于第一组数据111号点到达每个点的路径都是唯一自然无论怎么设置边权最短路都是唯一的。对于第二组数据因为k1k1k1所以两条边的边权都只能设置为111。111号点到222号点的最短路长度为111走两条边都可以所以不是唯一的。【数据范围】本题采用捆绑测试。对于20%20\%20%的数据n,m≤5n,m\leq 5n,m≤5。对于另外20%20\%20%的数据k1k1k1。对于另外20%20\%20%的数据mn−1mn-1mn−1。对于另外20%20\%20%的数据k109k10^9k109。对于100%100\%100%的数据n≥1n\ge 1n≥1m≥0m\ge 0m≥01≤∑n,∑m≤3×1051\le \sum n,\sum m\leq 3\times 10^51≤∑n,∑m≤3×1051≤k≤1091\leq k \leq 10^91≤k≤1091≤xi,yi≤n1\le x_i,y_i\le n1≤xi,yi≤n。C实现#includebits/stdc.husingnamespacestd;constintN3e510;intT,n,m,k,d[N];vectorpairint,intg[N];boolvis[N],tf;queueintq;intmain(){scanf(%d,T);while(T--){scanf(%d%d%d,n,m,k);tffalse;for(inti1;in;i)d[i]-1,g[i].clear();for(inti1,x,y;im;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()){intxq.front();q.pop();for(autotmp:g[x]){intytmp.first;if(d[y]!-1){if(d[y]d[x]1)tftrue;continue;}d[y]d[x]1;vis[tmp.second]true;q.push(y);}}if(k1tf){puts(No);continue;}puts(Yes);for(inti1;im;i)if(vis[i])cout1 \n[im];elsecoutk \n[im];}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容

相关新闻