![打卡信奥刷题（3382）用C++实现信奥题 P9813 [CCC 2015 S4] Convex Hull](images/news1.jpg)
P9813 [CCC 2015 S4] Convex Hull题目描述给定一个nnn个点mmm条边的无向图每条边有两个边权tit_{i}ti和hih_{i}hi。你需要找到一条从sss到ttt的路径满足路径上边的hih_{i}hi之和kkk且tit_{i}ti之和最小只需要输出这个最小值即可如果无法找到满足条件的路径输出−1-1−1。输入格式第一行三个整数k,n,mk,n,mk,n,m。接下来mmm行每行四个整数ui,vi,ti,hiu_{i},v_{i},t_{i},h_{i}ui,vi,ti,hi表示一条从uiu_{i}ui到viv_{i}vi的路径边权为{ti,hi}\{t_{i},h_{i}\}{ti,hi}。最后一行两个整数s,ts,ts,t。输出格式当存在满足条件的路径时输出一行一个整数表示满足条件的最小tit_{i}ti之和。否则输出一行−1-1−1。输入输出样例 #1输入 #110 4 7 1 2 4 4 1 3 7 2 3 1 8 1 3 2 2 2 4 2 1 6 3 4 1 1 1 4 6 12 1 4输出 #17输入输出样例 #2输入 #23 3 3 1 2 5 1 3 2 8 2 1 3 1 3 1 3输出 #2-1说明/提示【数据范围】对于20%20\%20%的数据k1k 1k12≤n≤2002 \leq n \leq 2002≤n≤200。对于另外20%20\%20%的数据k1k 1k12≤n≤2×1032 \leq n \leq 2 \times 10^{3}2≤n≤2×103。对于100%100\%100%的数据0≤hi≤2000 \leq h_{i} \leq 2000≤hi≤2001≤ti≤1051 \leq t_{i} \leq 10^{5}1≤ti≤1051≤k≤2001 \leq k \leq 2001≤k≤2002≤n≤2×1032 \leq n \leq 2 \times 10^{3}2≤n≤2×1031≤m≤1041 \leq m \leq 10^{4}1≤m≤104s≠ts \neq tst。C实现#includebits/stdc.husingnamespacestd;usinglllonglong;constintN2e310,M2e410;intn,m,k,s,t,d[N][210];inte[M],ne[M],h[N],w1[M],w2[M],idx;boolst[N][210];inlinevoidadd(inta,intb,intc,intd){e[idx]b,ne[idx]h[a],w1[idx]c,w2[idx]d,h[a]idx;}structnode{intw,f,id;booloperator(constnodet)const{returnwt.w;}};inlinevoiddijkstra(){memset(d,0x3f,sizeofd);memset(st,0,sizeofst);priority_queuenodeq;q.push({0,0,s});d[s][0]0;while(q.size()){node uq.top();q.pop();// coutu.id\n;if(st[u.id][u.f])continue;st[u.id][u.f]1;for(intih[u.id];i;ine[i]){intve[i];if(w2[i]u.fk)continue;if(d[v][u.fw2[i]]u.ww1[i])d[v][u.fw2[i]]u.ww1[i],q.push({u.ww1[i],u.fw2[i],v});}}}intmain(){scanf(%d%d%d,k,n,m);for(inti1;im;i){inta,b,c,d;scanf(%d%d%d%d,a,b,c,d);add(a,b,c,d),add(b,a,c,d);}scanf(%d%d,s,t);dijkstra();intans1e9;for(inti0;ik;i)ansmin(ans,d[t][i]);if(ans1e9)puts(-1);elsecoutans\n;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
打卡信奥刷题（3382）用C++实现信奥题 P9813 [CCC 2015 S4] Convex Hull
P9813 [CCC 2015 S4] Convex Hull题目描述给定一个nnn个点mmm条边的无向图每条边有两个边权tit_{i}ti和hih_{i}hi。你需要找到一条从sss到ttt的路径满足路径上边的hih_{i}hi之和kkk且tit_{i}ti之和最小只需要输出这个最小值即可如果无法找到满足条件的路径输出−1-1−1。输入格式第一行三个整数k,n,mk,n,mk,n,m。接下来mmm行每行四个整数ui,vi,ti,hiu_{i},v_{i},t_{i},h_{i}ui,vi,ti,hi表示一条从uiu_{i}ui到viv_{i}vi的路径边权为{ti,hi}\{t_{i},h_{i}\}{ti,hi}。最后一行两个整数s,ts,ts,t。输出格式当存在满足条件的路径时输出一行一个整数表示满足条件的最小tit_{i}ti之和。否则输出一行−1-1−1。输入输出样例 #1输入 #110 4 7 1 2 4 4 1 3 7 2 3 1 8 1 3 2 2 2 4 2 1 6 3 4 1 1 1 4 6 12 1 4输出 #17输入输出样例 #2输入 #23 3 3 1 2 5 1 3 2 8 2 1 3 1 3 1 3输出 #2-1说明/提示【数据范围】对于20%20\%20%的数据k1k 1k12≤n≤2002 \leq n \leq 2002≤n≤200。对于另外20%20\%20%的数据k1k 1k12≤n≤2×1032 \leq n \leq 2 \times 10^{3}2≤n≤2×103。对于100%100\%100%的数据0≤hi≤2000 \leq h_{i} \leq 2000≤hi≤2001≤ti≤1051 \leq t_{i} \leq 10^{5}1≤ti≤1051≤k≤2001 \leq k \leq 2001≤k≤2002≤n≤2×1032 \leq n \leq 2 \times 10^{3}2≤n≤2×1031≤m≤1041 \leq m \leq 10^{4}1≤m≤104s≠ts \neq tst。C实现#includebits/stdc.husingnamespacestd;usinglllonglong;constintN2e310,M2e410;intn,m,k,s,t,d[N][210];inte[M],ne[M],h[N],w1[M],w2[M],idx;boolst[N][210];inlinevoidadd(inta,intb,intc,intd){e[idx]b,ne[idx]h[a],w1[idx]c,w2[idx]d,h[a]idx;}structnode{intw,f,id;booloperator(constnodet)const{returnwt.w;}};inlinevoiddijkstra(){memset(d,0x3f,sizeofd);memset(st,0,sizeofst);priority_queuenodeq;q.push({0,0,s});d[s][0]0;while(q.size()){node uq.top();q.pop();// coutu.id\n;if(st[u.id][u.f])continue;st[u.id][u.f]1;for(intih[u.id];i;ine[i]){intve[i];if(w2[i]u.fk)continue;if(d[v][u.fw2[i]]u.ww1[i])d[v][u.fw2[i]]u.ww1[i],q.push({u.ww1[i],u.fw2[i],v});}}}intmain(){scanf(%d%d%d,k,n,m);for(inti1;im;i){inta,b,c,d;scanf(%d%d%d%d,a,b,c,d);add(a,b,c,d),add(b,a,c,d);}scanf(%d%d,s,t);dijkstra();intans1e9;for(inti0;ik;i)ansmin(ans,d[t][i]);if(ans1e9)puts(-1);elsecoutans\n;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
