当前位置：首页 > news >正文

打卡信奥刷题（3382）用C++实现信奥题 P9813 [CCC 2015 S4] Convex Hull

news 2026/6/13 7:57:09

P9813 [CCC 2015 S4] Convex Hull

题目描述

给定一个nnn个点，mmm条边的无向图，每条边有两个边权tit_{i}ti和hih_{i}hi。

你需要找到一条从sss到ttt的路径，满足路径上边的hih_{i}hi之和<k<k<k且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

输入 #1

10 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

输出 #1

输入输出样例 #2

输入 #2

3 3 3 1 2 5 1 3 2 8 2 1 3 1 3 1 3

输出 #2

-1

说明/提示

【数据范围】：

对于20%20\%20%的数据，k=1k = 1k=1，2≤n≤2002 \leq n \leq 2002≤n≤200。

对于另外20%20\%20%的数据，k=1k = 1k=1，2≤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≤200，1≤ti≤1051 \leq t_{i} \leq 10^{5}1≤ti≤105，1≤k≤2001 \leq k \leq 2001≤k≤200，2≤n≤2×1032 \leq n \leq 2 \times 10^{3}2≤n≤2×103，1≤m≤1041 \leq m \leq 10^{4}1≤m≤104，s≠ts \neq ts=t。

C++实现

#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;constintN=2e3+10,M=2e4+10;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<(constnode&t)const{returnw>t.w;}};inlinevoiddijkstra(){memset(d,0x3f,sizeofd);memset(st,0,sizeofst);priority_queue<node>q;q.push({0,0,s});d[s][0]=0;while(q.size()){node u=q.top();q.pop();// cout<<u.id<<"\n";if(st[u.id][u.f])continue;st[u.id][u.f]=1;for(inti=h[u.id];i;i=ne[i]){intv=e[i];if(w2[i]+u.f>=k)continue;if(d[v][u.f+w2[i]]>u.w+w1[i])d[v][u.f+w2[i]]=u.w+w1[i],q.push({u.w+w1[i],u.f+w2[i],v});}}}intmain(){scanf("%d%d%d",&k,&n,&m);for(inti=1;i<=m;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();intans=1e9;for(inti=0;i<k;i++)ans=min(ans,d[t][i]);if(ans==1e9)puts("-1");elsecout<<ans<<"\n";return0;}