打卡信奥刷题（3087）用C++实现信奥题 P7100 [W1] 团

P7100 [W1] 团题目描述我有一张nnn个节点的无向边带权图。它的边很多用这个方法表示有kkk个集合第iii个集合可以表示为Si{(T1,W1),(T2,W2),…,(T∣Si∣,W∣Si∣)}S_i\{(T_1,W_1),(T_2,W_2),\dots,(T_{|S_i|},W_{|S_i|})\}Si​{(T1​,W1​),(T2​,W2​),…,(T∣Si​∣​,W∣Si​∣​)}。对于任何两对(Ti,Wi),(Tj,Wj)(T_i,W_i),(T_j,W_j)(Ti​,Wi​),(Tj​,Wj​)在同一个集合里面图中会形成一条连TiT_iTi​和TjT_jTj​的边边权为WiWjW_iW_jWi​Wj​。请对于所有节点iii找到111到iii的最短路即从111到iii的边权和最小的简单路径。输入格式第一行两个正整数n,kn,kn,k。接下来描述kkk个集合。第iii集合的描述的第一行一个正整数∣Si∣|S_i|∣Si​∣表示∣Si∣|S_i|∣Si​∣的大小。接下来SiS_iSi​行每行两个正整数t,wt,wt,w表示(t,w)∈Si(t,w)\in S_i(t,w)∈Si​。输出格式一行nnn个正整数第iii个正整数表示111到iii的最短路长度。如果不存在一条路径输出0x3f3f3f3f3f3f3f3f4557430888798830399\textsf{0x3f3f3f3f3f3f3f3f}45574308887988303990x3f3f3f3f3f3f3f3f4557430888798830399。输入输出样例 #1输入 #15 2 3 1 1 2 1 5 3 3 2 1 3 2 4 1输出 #10 2 5 4 4说明/提示对于前10%10\%10%的数据∣Si∣2|S_i|2∣Si​∣2对于前20%20\%20%的数据∣Si∣≤10|S_i|\le10∣Si​∣≤10对于前50%50\%50%的数据∣N∣≤1000,∑∣Si∣≤2000|N|\le1000,\sum|S_i|\le2000∣N∣≤1000,∑∣Si​∣≤2000;对于100%100\%100%的数据1≤∣N∣≤2⋅105,∑∣Si∣≤4⋅105,0≤Wi≤1091\le|N|\le2\cdot10^5,\sum|S_i|\le4\cdot10^5,0\le W_i\le10^91≤∣N∣≤2⋅105,∑∣Si​∣≤4⋅105,0≤Wi​≤109。C实现#includebits/stdc.husingnamespacestd;typedeflonglongll;constintN4e55,MN2;constll INF0x3f3f3f3f3f3f3f3f;inttot,head[N],to[M],nxt[M];boolvis[N];ll cst[M],dis[N],b[N];intn,k,siz,x;ll y;intMid;structNode{ll x,dis;booloperator(constNoderhs)const{returnrhs.disdis;}};voidadd(intx,inty,ll z){to[tot]y,cst[tot]z,nxt[tot]head[x],head[x]tot;}voiddij(intu){priority_queueNodeq;for(inti1;iMid;i)dis[i]INF;dis[u]0;q.push(Node{u,0});while(!q.empty()){inttq.top().x;q.pop();if(vis[t])continue;vis[t]1;for(intihead[t];i;inxt[i]){intvto[i];if(dis[v]dis[t]cst[i]){dis[v]dis[t]cst[i];if(!vis[v])q.push(Node{v,dis[v]});}}}}intmain(){cinnk;Midn;for(inti1;ik;i){cinsiz;Mid;for(intj1;jsiz;j){cinxb[j];add(x,Mid,b[j]);add(Mid,x,b[j]);}}dij(1);for(inti1;in;i)coutdis[i] ;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容