好贷网好贷款

HDOJ 4725 - The Shortest Path in Nya Graph 构图最短路(priority_queue+dijkstra)

发布时间:2016-12-3 17:43:04 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDOJ 4725 - The Shortest Path in Nya Graph 构图最短路(priority_queue+dijkstra)",主要涉及到HDOJ 4725 - The Shortest Path in Nya Graph 构图最短路(priority_queue+dijkstra)方面的内容,对于HDOJ 4725 - The Shortest Path in Nya Graph 构图最短路(priority_queue+dijkstra)感兴趣的同学可以参考一下。

                   题意:                            有N个点..每个点在某个层上..而有些点直接也存在无向边..假设现在在点u..可以沿着u连的无向边走向其他点..也可以花C的距离代价走到其所在层的+1,-1层的任意点..问1~N的最短距离...                    题解:                            显然是构图最短路了..但是比赛的时候一直没搞对..队长提供了思路.是正确的..但我也没码出来..这里是参考了别人的思路...                            每个点是每个点.那么首先有N个点..然后把每一层拆成两个点..入点(i<<1|1)和出点(i<<1)..这就是2N个点..所以总共3N个点...                            1、对于每个点.向其层的出点做边.距离为0..其层的入点向其做边.距离为0....                            2、对于每一层..其出点向其+1/-1层做边.距离为C..                            3、根据题目所给的...两两间做边... Program: #include<iostream> #include<stack> #include<queue> #include<stdio.h> #include<algorithm> #include<string.h> #include<cmath> #define ll long long #define oo 1000000007 #define MAXN 201010 #define MAXM 801010 using namespace std; struct node { int u,v,d,next; }line[MAXM]; struct NODE { int u,dis; bool operator <(NODE a) const { return a.dis<dis; } }; int Lnum,_next[MAXN],dis[MAXN]; priority_queue<NODE> Q; void addline(int u,int v,int d) { line[++Lnum].next=_next[u],_next[u]=Lnum; line[Lnum].u=u,line[Lnum].v=v,line[Lnum].d=d; } bool used[MAXN]; int dijkstra(int s,int e) { NODE h,p; memset(dis,-1,sizeof(dis)); memset(used,false,sizeof(used)); h.u=s,dis[h.u]=h.dis=0,Q.push(h); while (!Q.empty()) { h=Q.top(),Q.pop(); if (used[h.u]) continue; used[h.u]=true; for (int k=_next[h.u];k;k=line[k].next) if (dis[line[k].v]==-1 || dis[line[k].v]>dis[h.u]+line[k].d) { dis[line[k].v]=dis[h.u]+line[k].d; p.u=line[k].v,p. dis=dis[line[k].v]; Q.push(p); } } return dis[e]; } int main() { int C,CA,cases,N,M,i,h,u,v,d,s,e; scanf("%d",&CA); for (cases=1;cases<=CA;cases++) { scanf("%d%d%d",&N,&M,&C); Lnum=0,memset(_next,0,sizeof(_next)); for (i=1;i<=N;i++) { scanf("%d",&d); addline(i,N+(d<<1),0),addline(N+(d<<1|1),i,0); } for (i=1;i<=N;i++) { addline(N+(i<<1),N+((i+1)<<1|1),C); addline(N+(i<<1),N+((i-1)<<1|1),C); } s=1,e=N; while (M--) { scanf("%d%d%d",&u,&v,&d); addline(u,v,d),addline(v,u,d); } printf("Case #%d: %d\n",cases,dijkstra(s,e)); } return 0; }

上一篇:再来一个动画!
下一篇:JVM中将MethodArea 作为PermannentArea管理的弊端

相关文章

相关评论