个人微企业网站模板,做服装有哪些好的网站,手机网站 百度推广,北京seo运营正题
luogu 4644 题目大意
给你一段时间#xff0c;有n头奶牛#xff0c;第i头可以花费sis_isi的代价清理lil_ili到rir_iri#xff0c;问你清理完所有时间段的最小代价 解题思路
所有点需求都为1的线性规划#xff0c;直接代入最短路就可以了 code
#includeq…正题
luogu 4644 题目大意
给你一段时间有n头奶牛第i头可以花费sis_isi的代价清理lil_ili到rir_iri问你清理完所有时间段的最小代价 解题思路
所有点需求都为1的线性规划直接代入最短路就可以了 code
#includequeue
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 100010
#define mp make_pair
#define fs first
#define sn second
using namespace std;
ll n,l,r,x,y,z,tot,p[N],b[N],h[N];
priority_queuepairll,ll d;
struct rec
{ll to,nx,l;
}e[N2];
void add(ll x,ll y,ll z)
{e[tot].toy;e[tot].lz;e[tot].nxh[x];h[x]tot;return;
}
bool dij()
{memset(b,127/3,sizeof(b));b[l] 0;d.push(mp(0,l));while(!d.empty()){ll ud.top().sn;d.pop();if(p[u])continue;p[u]1;for(int ih[u];i;ie[i].nx){ll ve[i].to;if(b[u]e[i].lb[v]){b[v]b[u]e[i].l;d.push(mp(-b[v],v));}}}return p[r1];
}
int main()
{scanf(%lld%lld%lld,n,l,r);for(int il;ir;i)add(i1,i,0);for(int i1;in;i){scanf(%lld%lld%lld,x,y,z);add(x,y1,z);}if(dij())printf(%lld,b[r1]);else puts(-1);return 0;
}
