分層圖最短路問題小記

本質(zhì)還是最短路問題只是開多了一維數(shù)組表示層次
模板：

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5 + 10; const int maxm = 2e5 + 10; const ll INF = 1e18; struct Edge{int to,next;ll w; }edge[maxm<<1]; int head[maxn],tot; void init(){tot = 0;memset(head,-1,sizeof(head)); }inline void addedge(int u,int v,ll w){edge[tot].to = v;edge[tot].next = head[u];edge[tot].w = w;head[u] = tot++; }struct Node{int index,level;ll dist;Node(int in = 0,int le = 0,ll d = 0){index = in, level = le, dist = d;}bool operator < (const Node & d) const{return dist > d.dist;}; }dis[maxn][11];bool vis[maxn][11]; int n, m, k;void dij(int s){for(int i = 0; i <= n; ++i){for(int j = 0; j <= k; ++j){dis[i][j].dist = INF;vis[i][j] = false;}}dis[s][0].dist = 0;priority_queue<Node>q;q.emplace(s,0,0);while(!q.empty()){Node cur = q.top(); q.pop();int u = cur.index, level = cur.level;if(vis[u][level]) continue ;vis[u][level] = 1;for(int i = head[u]; ~i; i = edge[i].next){int v = edge[i].to;ll cost = edge[i].w;if(dis[v][level].dist > dis[u][level].dist + cost){dis[v][level].dist = dis[u][level].dist + cost;q.emplace(v,level,dis[v][level].dist);}if(level + 1 <= k && dis[v][level+1].dist > dis[u][level].dist){dis[v][level+1].dist = dis[u][level].dist;q.emplace(v,level + 1,dis[v][level+1].dist);}}} }

入門題：
P4586
AC code：

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5 + 10; const int maxm = 2e5 + 10; const ll INF = 1e18; struct Edge{int to,next;ll w; }edge[maxm<<1]; int head[maxn],tot; void init(){tot = 0;memset(head,-1,sizeof(head)); }inline void addedge(int u,int v,ll w){edge[tot].to = v;edge[tot].next = head[u];edge[tot].w = w;head[u] = tot++; }struct Node{int index,level;ll dist;Node(int in = 0,int le = 0,ll d = 0){index = in, level = le, dist = d;}bool operator < (const Node & d) const{return dist > d.dist;}; }dis[maxn][11];bool vis[maxn][11]; int n, m, k;void dij(int s){for(int i = 0; i <= n; ++i){for(int j = 0; j <= k; ++j){dis[i][j].dist = INF;vis[i][j] = false;}}dis[s][0].dist = 0;priority_queue<Node>q;q.emplace(s,0,0);//vis[s][0] = 1;while(!q.empty()){Node cur = q.top(); q.pop();int u = cur.index, level = cur.level;//vis[u][level] = 0;if(vis[u][level]) continue ;vis[u][level] = 1;for(int i = head[u]; ~i; i = edge[i].next){int v = edge[i].to;ll cost = edge[i].w;if(dis[v][level].dist > dis[u][level].dist + cost){dis[v][level].dist = dis[u][level].dist + cost;//if(!vis[v][level])q.emplace(v,level,dis[v][level].dist);}if(level + 1 <= k && dis[v][level+1].dist > dis[u][level].dist){dis[v][level+1].dist = dis[u][level].dist;//if(!vis[v][level+1])q.emplace(v,level + 1,dis[v][level+1].dist);}}} }template <typename T> void read(T &x){x = 0;char c = getchar();for(;c < '0' || c > '9'; c = getchar());for(;c >= '0' && c <= '9'; c = getchar())x = (x << 1) + (x << 3) + (c ^ 48); }int main(){init();int u,v,s,t;ll w;read(n),read(m),read(k);read(s),read(t);++s,++t;for(int i = 0; i < m; ++i){read(u),read(v),read(w);++u,++v;addedge(u,v,w);addedge(v,u,w);}if(k >= m){puts("0");return 0;}dij(s);ll ans = INF;for(int i = 0; i <= k; ++i){ans = min(ans, dis[t][k].dist);}printf("%lld\n",ans);return 0; }

2018ICPC南京站網(wǎng)絡(luò)賽預(yù)賽L題

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5 + 10; const int maxm = 2e5 + 10; const ll INF = 1e18; struct Edge{int to,next;ll w; }edge[maxm<<1]; int head[maxn],tot; void init(){tot = 0;memset(head,-1,sizeof(head)); }inline void addedge(int u,int v,ll w){edge[tot].to = v;edge[tot].next = head[u];edge[tot].w = w;head[u] = tot++; }struct Node{int index,level;ll dist;Node(int in = 0,int le = 0,ll d = 0){index = in, level = le, dist = d;}bool operator < (const Node & d) const{return dist > d.dist;}; }dis[maxn][11];bool vis[maxn][11]; int n, m, k;void dij(){for(int i = 0; i <= n; ++i){for(int j = 0; j <= k; ++j){dis[i][j].dist = INF;vis[i][j] = false;}}dis[1][0].dist = 0;priority_queue<Node>q;q.emplace(1,0,0);while(!q.empty()){Node cur = q.top(); q.pop();int u = cur.index, level = cur.level;if(vis[u][level]) continue;vis[u][level] = true;for(int i = head[u]; ~i; i = edge[i].next){int v = edge[i].to;ll cost = edge[i].w;if(dis[v][level].dist > dis[u][level].dist + cost){dis[v][level].dist = dis[u][level].dist + cost;q.emplace(v,level,dis[v][level].dist);}if(level + 1 <= k && dis[v][level+1].dist > dis[u][level].dist){dis[v][level+1].dist = dis[u][level].dist;q.emplace(v,level + 1,dis[v][level+1].dist);}}} }template <typename T> void read(T &x){x = 0;char c = getchar();for(;c < '0' || c > '9'; c = getchar());for(;c >= '0' && c <= '9'; c = getchar())x = (x << 1) + (x << 3) + (c ^ 48); }int main(){int T,u,v;ll w;read(T);while(T--){init();read(n),read(m),read(k);for(int i = 0; i < m; ++i){read(u),read(v),read(w);addedge(u,v,w);}if(k >= m){puts("0");continue ;}dij();ll ans = INF;for(int i = 0; i <= k; ++i){ans = min(ans, dis[n][k].dist);}printf("%lld\n",ans);}return 0; }

P3831 回家的路
題意：在一個(gè)n?n的網(wǎng)格圖中乘坐地鐵，每坐一站路就耗2分鐘，如果想從橫向x改為縱向y，必須從一些特殊的點(diǎn)進(jìn)行換乘，每次換乘耗時(shí)1分鐘。給定起點(diǎn)(sx,sy)終點(diǎn)(ex,ey)，求最花費(fèi)的最短時(shí)間。
思路：分層圖思想，將網(wǎng)格圖分成兩層，對每個(gè)車站點(diǎn)拆點(diǎn)，拆成兩個(gè)點(diǎn)，第一個(gè)點(diǎn)屬于第一層橫向網(wǎng)絡(luò)，只在x方向跑，第二個(gè)點(diǎn)是第二層縱向網(wǎng)絡(luò)，在y中跑，兩個(gè)點(diǎn)即兩層之間連一條邊(權(quán)值位1)，同一層不同點(diǎn)連邊權(quán)值為2，跑起點(diǎn)到終點(diǎn)的最短路即可。特殊地注意起點(diǎn)到起點(diǎn)的換乘，終點(diǎn)到終點(diǎn)的換乘，連權(quán)值為0的邊。
再注意一下將數(shù)組開大一點(diǎn)！！！

AC code：

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const int maxn = 1200000 + 100; struct Edge{int to,next,w; }edge[maxn<<1]; int n, m , tot, head[maxn]; void init(){tot = 0;memset(head,-1,sizeof(head)); }inline void addedge(int u,int v,int w){edge[tot].to = v;edge[tot].next = head[u];edge[tot].w = w;head[u] = tot++;//undirectededge[tot].to = u;edge[tot].next = head[v];edge[tot].w = w;head[v] = tot++; } struct Node{int id;ll dis;Node(int idd = 0,ll dd = INF){id = idd, dis = dd;}bool operator < (const Node &d) const {return dis > d.dis;} }d[maxn];bool vis[maxn]; void dijkstra(int s){int up = 2 * m + 5;for(int i = 0; i < up; ++i) vis[i] = 0 , d[i].id = i , d[i].dis = INF;priority_queue<Node>q;q.emplace(s,0);d[s].dis = 0;while(!q.empty()){int u = q.top().id; q.pop();if(vis[u]) continue ;vis[u] = 1;for(int i = head[u]; ~i; i = edge[i].next){int v = edge[i].to;if(d[v].dis > d[u].dis + edge[i].w){d[v].dis = d[u].dis + edge[i].w;q.emplace(v,d[v].dis);}}}return ; }struct Station{int id,x,y; }p[100100];//排序處理第一層，層內(nèi)跑時(shí)間花費(fèi)比較大，所以同一層內(nèi)盡量少的經(jīng)過車站，在不同層換乘 bool cmp1(const Station &a,const Station &b){if(a.x == b.x) return a.y < b.y;return a.x < b.x; }bool cmp2(const Station &a, const Station &b){if(a.y == b.y) return a.x < b.x;return a.y < b.y; }template <typename T> void read(T &x){x = 0;char c = getchar();int p = 1;for(; c <'0' || c >'9'; c = getchar()) if(c == '-') p = -1;for(; c >='0' && c <='9'; c = getchar())x = (x << 1) + (x << 3) + (c ^ 48);x *= p; }int main(){init();read(n),read(m);int s = m + 1, t = m + 2; //增加起點(diǎn)車站和終點(diǎn)車站的編號m += 2; //m要加2for(int i = 1; i <= m; ++i){read(p[i].x),read(p[i].y), p[i].id = i;}sort(p+1,p+1+m,cmp1); //排序處理第一層for(int i = 1; i <= m; ++i){if(p[i].x == p[i+1].x){addedge(p[i].id,p[i+1].id,abs(p[i+1].y - p[i].y) * 2);}}sort(p+1,p+1+m,cmp2);//排序處理第二層for(int i = 1; i <= m; ++i){if(p[i].y == p[i+1].y){addedge(p[i].id + m,p[i+1].id + m,abs(p[i+1].x - p[i].x) * 2);}}for(int i = 1; i <= m; ++i){addedge(p[i].id,p[i].id + m,1);}addedge(s,s + m,0);//起點(diǎn)到起點(diǎn)的換乘不需要連權(quán)值為1的邊。addedge(t,t + m,0);dijkstra(s);printf("%lld\n",d[t].dis != INF ? d[t].dis : -1);return 0; }

總結(jié)

以上是生活随笔為你收集整理的分层图最短路问题小记的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。