锐客网

  1. 首页 > 睿知 > it技术 > >

BZOJ 2100: [Usaco2010 Dec]Apple Delivery

IT知识deliveryappleUSACO

从来好事天生俭，自古瓜儿苦后甜。这篇文章主要讲述BZOJ 2100: [Usaco2010 Dec]Apple Delivery相关的知识，希望能为你提供帮助。
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2100
解：
【BZOJ 2100: [Usaco2010 Dec]Apple Delivery】典型的最短路，从两个点都跑一遍模板就好了，不过有点麻烦的是，如果跑dijkstra，要用堆来优化，如果跑spfa要用SLF（当然习惯用LLL也行）来优化，总之不能裸的模板去跑。
程序：

#include< iostream> #include< cstdio> #include< cstring> #include< queue> #define INF 2100000000 using namespace std; struct ding{ int to,w,next; }edge[400010]; struct ding2{ int p,di; bool operator< (const ding2& a) const { return a.di< di; } }; int cnt,ans,n,m; int head[100010],dis[100010]; priority_queue< ding2> q; void add(int u,int v,int d){edge[++cnt].to=v; edge[cnt].w=d; edge[cnt].next=head[u]; head[u]=cnt; } void dijkstra(int st) { for (int i=1; i< =n; i++) dis[i]=INF; q.push((ding2){st,0}); dis[st]=0; while (!q.empty()) { ding2 now=q.top(); q.pop(); if (now.di!=dis[now.p]) continue; for (int i=head[now.p]; i; i=edge[i].next) { int k=edge[i].to; if (dis[k]> now.di+edge[i].w) { dis[k]=now.di+edge[i].w; q.push((ding2){k,dis[k]}); } } } } int main() { int st,en1,en2; scanf("%d%d%d%d%d",& m,& n,& st,& en1,& en2); int x,y,d; for (int i=1; i< =m; i++) { scanf("%d%d%d",& x,& y,& d); add(x,y,d); add(y,x,d); } dijkstra(en1); ans+=dis[en2]+dis[st]; dijkstra(en2); ans=min(ans,dis[en1]+dis[st]); printf("%d\n",ans); return 0; }

 

    推荐阅读


    上一篇：android图片文件的路径地址与Uri的相互转换

    下一篇：android - Fragment getView() 总是返回null