【bzoj2834】【回家的路】【最短路】

Description

Input

Output

Sample Input

Sample Output

HINT

N<=20000,M<=100000

题解：

          把图拆成两层,一层横着进行,一层竖着进行,通过可以换乘的点连接两层.

          然后直接跑最短路即可。

代码:

#include
#include
#include
#include
#define N 200010
#define M 400010
using namespace std;
struct use{int x,y,id;}p[N];
struct edge{int st,en;long long v;}e[M<<1];
int point[N],next[M<<1],n,m;
int f[N],q[N*20],cnt;
long long dis[N];
bool cmp1(use a,use b){return a.xdis[u]+e[i].v){dis[e[i].en]=dis[u]+e[i].v;if (!f[e[i].en]){f[e[i].en]=1;q[++t]=e[i].en;}}}
}
int main(){scanf("%d%d",&n,&m);for (int i=1;i<=m+2;i++){scanf("%d%d",&p[i].x,&p[i].y);p[i].id=i;}	sort(p+1,p+m+3,cmp1);for (int i=1;i<=m+1;i++) if (p[i].x==p[i+1].x) add(p[i].id,p[i+1].id,(long long)(p[i+1].y-p[i].y)*2);sort(p+1,p+m+3,cmp2);for (int i=1;i<=m+1;i++)if (p[i].y==p[i+1].y) add(m+2+p[i].id,m+2+p[i+1].id,(long long)(p[i+1].x-p[i].x)*2);sort(p+1,p+m+3,cmp3);for (int i=1;i<=m;i++)add(i,i+m+2,1);add(m+1,m+1+m+2,0);spfa(m+1);cout<

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