题目描述

给定n × n的网格图，每走一条边花费为2，只能在给定交叉点转向花费为1，询问从起点 走到终点的最小花费。

思路

经典分层图最短路
每层分别连接横向和纵向边表示走边的花费，层与层之间连边表示转向的花费。

做法

首先想到把图上所有的点暴力建出来并连边跑最短路，但n²的点数太多会MLE爆掉。
考虑优化，因为转向总是在换乘点进行的，所以可以只把每个换程站,起点和终点建出来并互相连边
连边时可以按横或纵坐标进行排序来快速找出两个点是否在同一直线上
之后连边跑最短路即可

AC代码

#include<bits/stdc++.h>
#define int long long
#define pli pair<int , int>
using namespace std;
const int N = 1e6 + 10; 

struct edge{
    int x , y;
    int id;
} a[N];

int n , m;
int h[N] , tot;
struct node{
    int to , nxt , dis;
} e[N];

inline void add(int u , int v , int w){
    e[++tot].to = v;
    e[tot].dis = w;
    e[tot].nxt = h[u];
    h[u] = tot;
}

inline bool cmp1(edge q , edge p){
    if(q.x == p.x) return q.y < p.y;
    return q.x < p.x;
}

inline bool cmp2(edge q , edge p){
    if(q.y == p.y) return q.x < p.x;
    return q.y < p.y;
}

int dis[N];
bool v[N];
priority_queue<pli , vector<pli> , greater<pli> > G;
inline void Dijkstra(int s){
    memset(dis , 0x3f , sizeof(dis));
    dis[s] = 0;
    G.push({dis[s] , s});
    while(!G.empty()){
        int x = G.top().second;
        G.pop();
        if(v[x]) continue;
        v[x] = 1;
        for (int i = h[x] ; i ; i = e[i].nxt){
            int y = e[i].to , w = e[i].dis;
            if(dis[y] > dis[x] + w){
                dis[y] = dis[x] + w;
                G.push({dis[y] , y});
            }
        }   
    }
}

signed main(){
    ios::sync_with_stdio(false) , cin.tie(0);
    cin >> n >> m;
    if(m == 0) {//其实加不加无所谓
        cout << -1;
        return 0;
    }
    int s = m + 1 , t = m + 2;
    for (int i = 1 ; i <= m + 2 ; i++){//所有点一起读入
        cin >> a[i].x >> a[i].y;
        a[i].id = i;
    }

    sort(a + 1 , a + 3 + m , cmp1);//建立纵边
    for (int i = 1 ; i <= m + 1 ; i++){
        if(a[i].x == a[i + 1].x){
            add(a[i].id , a[i + 1].id , (a[i + 1].y - a[i].y) * 2);
            add(a[i + 1].id , a[i].id , (a[i + 1].y - a[i].y) * 2);
        }
    }

    sort(a + 1 , a + 3 + m , cmp2);//建立横边
    for (int i = 1 ; i <= m + 1 ; i++){
        if(a[i].y == a[i + 1].y){
            add(a[i].id + m + 2, a[i + 1].id + m + 2, (a[i + 1].x - a[i].x) * 2);
            add(a[i + 1].id + m + 2, a[i].id + m + 2, (a[i + 1].x - a[i].x) * 2);
        }
    }   

    for (int i = 1 ; i <= m ; i++){//两层的转向点连边
        add(i , i + m + 2 , 1);
        add(i + m + 2 , i , 1);
    }

    add(m + 1 , m * 2 + 3 , 0);
    add(m * 2 + 3 , m + 1 , 0);//上下层起点
    add(m + 2 , m * 2 + 4 , 0);
    add(m * 2 + 4 , m + 2 , 0);//上下层终点

    Dijkstra(s);
    if(dis[t] >= 0x3f3f3f3f) cout << -1 << "\n";
    else cout << dis[t];

    return 0;
}