C++课后习题训练记录Day146

1.练习项目 问题描述”大鱼吃小鱼小鱼吃虾米。“但是小鱼也有变成大鱼的梦想小鱼住在一个有 n 个区域的海底世界区域编号从 1 到 n海底世界中有 m 条单向通道每条通道连接了其中两个区域。区域 1 有海底世界中唯一的虾米群。区域 2 到 n 中有 k 个区域可以作为出生点即小鱼可以任意选择其中一个区域作为起点它将从该起点出发游到区域 1从而吃到虾米群变成大鱼。现在小鱼希望选择某个出生点使得它从该出生点出发到吃到虾米群的总距离最短。请你帮帮它。输入格式第一行一个整数 t表示测试案例的个数。1≤t≤10对于每个测试案例第一行三个整数 n,m,k表示海底世界的区域个数、单向通道条数、出生点个数。2≤n≤1041≤m≤1041≤k≤n−1​第二行k 个整数表示出生点的编号 vi​。2≤vi≤n接下来 m 行每行三个整数 a,b,c表示存在一条从区域 a 到区域 b 的长度为 c 的单向通道。1≤a,b≤n1≤c≤105输出格式共 t 行每行一个整数表示吃到虾米的最短距离若无论取哪个出生点都无法吃到虾米则为 −1。2.选择课程在蓝桥云课中选择题库选择题号19849并开始练习。3.开始练习1虚拟源点 #includebits/stdc.husing namespace std;using ll long long;const ll N 1e410;const ll inf 2e18;struct Edge{ll x,w;bool operator (const Edge u)const{return (w u.w ? x u.x:w u.w);}};vectorEdgeg[N];ll d[N],n,m,k;void dijkstra(){//初始化for(int i0;in;i)d[i]inf;//变量priority_queueEdgepq;bitsetNvis;pq.push({0,d[0]0});//循环pqwhile(pq.size()){//拓展松弛int xpq.top().x;pq.pop();if(vis[x])continue;vis[x]true;for(const autot:g[x]){int yt.x;int wt.w;if(d[x]wd[y]){//说明st ... y这条边可以被st ... x y松弛掉pq.push({y,d[y]d[x]w});}}}}int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t;cint;while(t--){cinnmk;for(int i0;in;i)g[i].clear();for(int i1;ik;i){int x;cinx;g[0].push_back({x,0});}for(int i1;im;i){ll x,y,w;cinxyw;g[x].push_back({y,w});}dijkstra();if(d[1]inf)cout-1\n;else coutd[1]\n;}return 0;}2反图#includebits/stdc.husing namespace std;using ll long long;const ll N 1e410;const ll inf 2e18;struct Edge{ll x,w;bool operator (const Edge u)const{return (w u.w ? x u.x:w u.w);}};vectorEdgeg[N];ll d[N],n,m,k;void dijkstra(){//初始化for(int i1;in;i)d[i]inf;//变量priority_queueEdgepq;bitsetNvis;pq.push({1,d[1]0});//循环pqwhile(pq.size()){//拓展松弛int xpq.top().x;pq.pop();if(vis[x])continue;vis[x]true;for(const autot:g[x]){int yt.x;int wt.w;if(d[x]wd[y]){//说明st ... y这条边可以被st ... x y松弛掉pq.push({y,d[y]d[x]w});}}}}int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t;cint;while(t--){cinnmk;for(int i1;in;i)g[i].clear();vectorintv;for(int i1;ik;i){int x;cinx;v.push_back(x);}for(int i1;im;i){ll x,y,w;cinxyw;g[y].push_back({x,w});}dijkstra();ll ansinf;for(const autox:v)ansmin(ans,d[x]);if(ansinf)cout-1\n;else coutans\n;}return 0;}2检验结果对此代码进行检验检验后无报错提交此代码判题结果为正确100分。3练习心得注意每段代码末尾的分号是否存在 如不存在则需即使补充输入法 是否切换 为英语模式语法是否错误。