10.19图论专题解题报告

题目:Problem

3.最短路

貌似也就这道题能看得懂了

其实还是Google了一下的

首先对点分别按x坐标进行排序

然后在每相邻两个点之间连一条边 距离为Xi+1-Xi

y坐标也进行相似操作

为什么不要连其他的呢?

证:因为Xi到Xi+2的距离必然等于Xi到Xi+1的距离再到Xi+2的距离

所以并不需要连那么多

 

于是连好边就可以Dijkstra了

边数并不多 这样就能过了

// <dist.cpp> – 10/19/15 08:28:18
// This file is created by XuYike’s black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don’t know what this program is.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
int res=0;
char ch=getchar();
while(ch<‘0’||ch>’9′)ch = getchar();
while(ch>=’0’&&ch<=’9’)res=res*10+ch-‘0’,ch=getchar();
return res;
}
struct point{
int i,x,y;
}p[200001];
struct bian{
int v,next;
bool operator <(bian b) const {return v>b.v;}
bool operator >(bian b) const {return v<b.v;}
};
bool cmpx(point a,point b){
return a.x<b.x;
}
bool cmpy(point a,point b){
return a.y<b.y;
}
vector <bian> k[200001];
priority_queue <bian> h;
bool geng[200001];
int dist[200001];
int main()
{
freopen(“dist.in”,”r”,stdin);
freopen(“dist.out”,”w”,stdout);
int n=getint();
for(int i=0;i<n;i++)p[i].i=i,p[i].x=getint(),p[i].y=getint();//输入

sort(p,p+n,cmpx);
for(int i=0;i<n-1;i++){
int v=p[i+1].x-p[i].x;
bian b={v,p[i+1].i},a={v,p[i].i};
k[p[i].i].push_back(b);
k[p[i+1].i].push_back(a);
}
sort(p,p+n,cmpy);
for(int i=0;i<n-1;i++){
int v=p[i+1].y-p[i].y;
bian b={v,p[i+1].i},a={v,p[i].i};
k[p[i].i].push_back(b);
k[p[i+1].i].push_back(a);
}//连边

for(int i=1;i<n;i++)dist[i]=2147483647;
bian NEW={0,0};
h.push(NEW);
for(int i=1;i<n;i++){
while(geng[h.top().next])h.pop();
int now=h.top().next;
h.pop();
int l=k[now].size();
for(int o=0;o<l;o++){
if(dist[now]+k[now][o].v<dist[k[now][o].next]){
dist[k[now][o].next]=dist[now]+k[now][o].v;
bian NEW={dist[k[now][o].next],k[now][o].next};
h.push(NEW);
}
}
geng[now]=1;
}//Dijkstra

cout<<dist[n-1];//输出
return 0;
}

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz