BZOJ 2834: 回家的路 Dijkstra

按照横，竖为方向跑一个最短路即可，算是水题~ 

#include     
#define N 200005    
#define E 2000000 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;      
int n,m,tot,edges,s,T;     
int hd[E],to[E],nex[E],val[E],d[E],done[E],id[E][2];            
void addedge(int u,int v,int c) 
{nex[++edges]=hd[u],hd[u]=edges,to[edges]=v,val[edges]=c;     
}
struct Point
{int x,y,id;   Point(int x=0,int y=0):x(x),y(y){}   
}t[N];     
struct Node
{int u,dis; Node(int u=0,int dis=0): u(u),dis(dis){} bool operator<(Node b) const {return b.disq;     
bool cmpx(Point a,Point b) 
{return a.x==b.x?a.y d[u] + val[i]) {d[v] = d[u] + val[i]; q.push(Node(v, d[v]));      }}}
}
int main() 
{  int i,j,k;  // setIO("input");  scanf("%d%d",&n,&m);         for(i=2;i<=m+1;++i) { scanf("%d%d",&t[i].x,&t[i].y);    id[i][0]=++tot;   id[i][1]=++tot;                   t[i].id=i;     }    scanf("%d%d",&t[1].x,&t[1].y); id[1][0]=++tot; id[1][1]=++tot;  t[1].id=1;m+=2;            scanf("%d%d",&t[m].x,&t[m].y); id[m][0]=++tot; id[m][1]=++tot;  t[m].id=m;            for(i=1;i<=m;++i) {addedge(id[i][0],id[i][1],1); addedge(id[i][1],id[i][0],1);   }sort(t+1,t+1+m,cmpx);  for(i=1;i<=m;i=j) {for(j=i;j<=m&&t[j].x==t[i].x;++j);    for(k=i+1;k

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！