本文主要是介绍P3831 [SHOI2012]回家的路 （分层图最短路），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：https://www.luogu.org/problem/P3831
一个网格图，横向或纵向走一边用时2，在特定点转向用时1，问从起点到终点用时最短为多少。
Solution：
虽然题目给出一个网格图，但是实际有用的点就是起点，终点和能换乘的点三种点，其余的点都可以忽略。
考虑分层图，第一层为横走向，第二层为纵走向，中间为转向所花的代价。
代码：
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
const int INF = 0x3f3f3f3f;
const int MAXN = 100009 * 2;
const int MAXM = 1000090;
int n, m;
int start, ende;
struct node
{int x, y, id;
}a[MAXN];
bool cmp_x(node a, node b)
{if(a.x == b.x) return a.y < b.y;return a.x < b.x;
}
bool cmp_y(node a, node b)
{if(a.y == b.y) return a.x < b.x;return a.y < b.y;
}
struct Edge
{int to, w, nxt;
}edge[MAXM];
int head[MAXN], t = 1;
void init()
{memset(head, -1, sizeof(head));t = 1;
}
void addEdge(int u, int v, int w)
{edge[t].to = v;edge[t].w = w;edge[t].nxt = head[u];head[u] = t++;
}
int dis[MAXN], book[MAXN];
void dijkstra()
{memset(dis, INF, sizeof(dis)); dis[start] = 0;memset(book, 0, sizeof(book));priority_queue<pii, vector<pii>, greater<pii> > q;q.push({dis[start], start});while(!q.empty()){int u = q.top().second;q.pop();if(book[u]) continue;book[u] = 1;for(int i = head[u]; i != -1; i = edge[i].nxt){int to = edge[i].to;int w = edge[i].w;if(!book[to] && dis[to] > dis[u] + w){dis[to] = dis[u] + w;q.push({dis[to], to});}}}
}
int main()
{cin >> n >> m;init();n = m + 2; //一共有m+2个点start = n - 1; ende = n; //起点和终点for(int i = 1; i <= n; i++){cin >> a[i].x >> a[i].y;a[i].id = i;}sort(a + 1, a + 1 + n, cmp_x); //以横坐标排序for(int i = 2; i <= n; i++)//建立第一层，横走向{if(a[i].x == a[i - 1].x) //如果两点横坐标相同，则在两点之间连边，边的权值就是这两个点相互到达所需时间{addEdge(a[i].id, a[i - 1].id, (a[i].y - a[i - 1].y) * 2);addEdge(a[i - 1].id, a[i].id, (a[i].y - a[i - 1].y) * 2);}}sort(a + 1, a + 1 + n, cmp_y);for(int i = 2; i <= n; i++) //建立第二层，纵走向{if(a[i].y == a[i - 1].y){addEdge(a[i].id + n, a[i - 1].id + n, (a[i].x - a[i - 1].x) * 2);addEdge(a[i - 1].id + n, a[i].id + n, (a[i].x - a[i - 1].x) * 2);}}for(int i = 1; i <= n - 2; i++) //两层之间，由 横向转为纵向 或 由纵向转为横向 的花费{addEdge(i, i + n, 1);addEdge(i + n, i, 1);}addEdge(start, start + n, 0); //在起点和终点转向不需花费addEdge(start + n, start, 0);addEdge(ende, ende + n, 0);addEdge(ende + n, ende, 0);dijkstra();if(dis[ende] == INF) cout << -1 << endl;else cout << dis[ende] << endl;return 0;}
这篇关于P3831 [SHOI2012]回家的路 （分层图最短路）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
