bzoj 2834: 回家的路

题目

F.A.Qs	Home	Discuss	ProblemSet	Status	Ranklist	Contest	入门OJ	ModifyUser  DCOI	Logout	捐赠本站

Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:替用户ir1d发布如下信息,希望大家能够积极支持。 OI Wiki 致力于成为一个开放*的 OI 知识整合站点，欢迎感兴趣的同学参与贡献 https://oi-wiki.org

2834: 回家的路

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 183  Solved: 98
[Submit][Status][Discuss]

Description

Input

Output

Sample Input

2 1
1 2
1 1 2 2

Sample Output

5

HINT

N<=20000,M<=100000

Source

[Submit][Status][Discuss]

HOME Back

---

한국어  中文  فارسی  English  ไทย

版权所有 ©2008-2018 大视野在线测评 | 湘ICP备13009380号

Based on opensource project hustoj.

解法

分层图最短路，将横向与纵向分开即可。

但是只能存下可转移的点与起点和终点。

数据好像有点水，起点和终点好像一定可以换乘

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cctype>
#include <vector>
#include <queue>
#define INF 2139062143
#define MAX 0x7ffffffffffffff
#define del(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
template<typename T>
inline void read(T&x)
{
    x=;T k=;char c=getchar();
    while(!isdigit(c)){if(c=='-')k=-;c=getchar();}
    while(isdigit(c)){x=x*+c-'';c=getchar();}x*=k;
}
const int maxn=+;
int n,m,s,t,ecnt[];
struct Q{
    int x,y,id;
}a[maxn];

struct Edge {
    int u,v,w;
    Edge(int u=,int v=,int w=):u(u),v(v),w(w) {}
};
vector<Edge> edge[];
vector<int> G[maxn][];
inline void add_edge(int u,int v,int w,int id) {
    edge[id].push_back(Edge(u,v,w));
    edge[id].push_back(Edge(v,u,w));
    ecnt[id]+=;
    G[u][id].push_back(ecnt[id]-);
    G[v][id].push_back(ecnt[id]-);
}

priority_queue< pair<pair<int,int>,int> > q;
int dis[maxn][];
bool vis[maxn][];

inline void dij() {
    del(dis,);dis[s][]=dis[s][]=;
    q.push(make_pair(make_pair(,s),));
    q.push(make_pair(make_pair(,s),));
    while(!q.empty()) {
        pair<pair<int,int>,int> Node=q.top();q.pop();
        pair<int,int> node=Node.first;
        int id=Node.second,u=node.second,d=-node.first;
        if(vis[u][id]) continue;
        vis[u][id]=;
        for(int i=;i<G[u][id].size();i++) {
            Edge& e=edge[id][G[u][id][i]];
            int v=e.v;
            if(dis[v][id]>d+e.w) {
                dis[v][id]=d+e.w;
                q.push(make_pair(make_pair(-dis[v][id],v),id));
            }
            if(dis[v][id^]>d+e.w+) {
                dis[v][id^]=d+e.w+;
                q.push(make_pair(make_pair(-dis[v][id^],v),id^));
            }
        }
    }
    printf("%d\n",(min(dis[m+][],dis[m+][])==INF)?-:min(dis[m+][],dis[m+][]));
}

bool cmp1(Q a,Q b) {
    return (a.x^b.x)?a.x<b.x:a.y<b.y;
}

bool cmp2(Q a,Q b) {
    return (a.y^b.y)?a.y<b.y:a.x<b.x;
}

bool cmp3(Q a,Q b) {
    return a.id<b.id;
}

int main()
{
    read(n),read(m);
    for(int i=;i<=m;i++) {read(a[i].x),read(a[i].y);a[i].id=i;}
    read(a[m+].x),read(a[m+].y);read(a[m+].x),read(a[m+].y);a[m+].id=m+;a[m+].id=m+;
    sort(a+,a++m+,cmp1);
    for(int i=;i<m+;i++) if(a[i].x==a[i+].x) add_edge(a[i].id,a[i+].id,*(a[i+].y-a[i].y),);
    sort(a+,a++m+,cmp2);
    for(int i=;i<m+;i++) if(a[i].y==a[i+].y) add_edge(a[i].id,a[i+].id,*(a[i+].x-a[i].x),);
    s=m+;
    dij();
    return ;
}