厦门网站制作推广,网站的营销功能,做外贸网站特色,做个商城网站怎么做便宜分层最短路算法是在SPFA算法的基础上#xff0c;将每个点分成若干层#xff0c;从而使得每个点之间的转移只在同一层次或上下两个相邻层次之间进行#xff0c;减少了每轮的迭代次数#xff0c;优化了算法的效率。
#include iostream
#include cstdio
#inc…分层最短路算法是在SPFA算法的基础上将每个点分成若干层从而使得每个点之间的转移只在同一层次或上下两个相邻层次之间进行减少了每轮的迭代次数优化了算法的效率。
#include iostream
#include cstdio
#include cstring
#include queueusing namespace std;const int MAXN 10005;
const int MAXM 100005;
const int INF 0x3f3f3f3f;struct Edge {int to, nxt, w;
} e[MAXM];int head[MAXN], tot;
int dis[MAXN], vis[MAXN];inline void add(int u, int v, int w) {e[tot].nxt head[u];e[tot].to v;e[tot].w w;head[u] tot;
}void spfa(int s) {memset(dis, 0x3f, sizeof(dis));dis[s] 0;queueint q;q.push(s);while (!q.empty()) {int u q.front();q.pop();vis[u] false;for (int i head[u]; i; i e[i].nxt) {int v e[i].to;if (dis[v] dis[u] e[i].w) {dis[v] dis[u] e[i].w;if (!vis[v]) {q.push(v);vis[v] true;}}}}
}int main() {int n, m;scanf(%d%d, n, m);tot 0;memset(head, 0, sizeof(head));for (int i 1; i m; i) {int u, v, w;scanf(%d%d%d, u, v, w);add(u, v, w);}int s, t;scanf(%d%d, s, t);spfa(s);printf(%d\n, dis[t]);return 0;
}int layer[MAXN]; //记录每个点所在的层次
int check_layer[MAXN]; //记录每个点是否在队列中void layer_spfa(int s) {memset(dis, 0x3f, sizeof(dis));dis[s] 0;layer[s] 0;queueint q;q.push(s);check_layer[s] true;while (!q.empty()) {int u q.front();q.pop();check_layer[u] false;for (int i head[u]; i; i e[i].nxt) {int v e[i].to;if (layer[u] layer[v]) {if (dis[v] dis[u] e[i].w) {dis[v] dis[u] e[i].w;if (!check_layer[v]) {q.push(v);check_layer[v] true;}}} else if (layer[v] layer[u]) { //分层if (dis[v] dis[u] e[i].w) {dis[v] dis[u] e[i].w;layer[v] layer[u] 1;if (!check_layer[v]) {q.push(v);check_layer[v] true;}}}}}
}先看题目
Alice 和 Bob 现在要乘飞机旅行他们选择了一家相对便宜的航空公司。该航空公司一共在 nn 个城市设有业务设这些城市分别标记为 00 到 n-1n−1一共有 mm 种航线每种航线连接两个城市并且航线有一定的价格。
Alice 和 Bob 现在要从一个城市沿着航线到达另一个城市途中可以进行转机。航空公司对他们这次旅行也推出优惠他们可以免费在最多 kk 种航线上搭乘飞机。那么 Alice 和 Bob 这次出行最少花费多少
输入格式
第一行三个整数 n,m,kn,m,k分别表示城市数航线数和免费乘坐次数。
接下来一行两个整数 s,ts,t分别表示他们出行的起点城市编号和终点城市编号。
接下来 mm 行每行三个整数 a,b,ca,b,c表示存在一种航线能从城市 aa 到达城市 bb或从城市 bb 到达城市 aa价格为 cc。
输出格式
输出一行一个整数为最少花费。
输入样例
5 6 1
0 4
0 1 5
1 2 5
2 3 5
3 4 5
2 3 3
0 2 100
输出样例
8
先给出具体代码
#includecstring
#includeiostream
#includequeueusing namespace std;typedef pairint, int PII;const int N 2100010, INF 0x3f3f3f3f;int n, m, k, s, t;
int dist[N];
int h[N], w[N], e[N], ne[N], idx;
bool st[N];void add(int a, int b, int c)
{e[idx] b, w[idx] c, ne[idx] h[a], h[a] idx ;
}void dijkstra(int u)
{memset(dist, INF, sizeof dist);dist[u] 0;priority_queuePII, vectorPII, greaterPII heap;heap.push({0, u});while(heap.size()){auto t heap.top();heap.pop();int ver t.second ,distance t.first;if(st[ver]) continue;st[ver] true;for(int i h[ver]; ~i; i ne[i]){int j e[i];if(dist[j] distance w[i]){dist[j] distance w[i];heap.push({dist[j], j});}}}
}int main()
{cin n m k s t;memset(h, -1, sizeof h);while(m --){int a, b, c;scanf(%d%d%d, a, b ,c);add(a, b, c), add(b, a, c);for(int j 1; j k; j ){add(j * n a, j * n b, c);add(j * n b, j * n a, c);add((j - 1) * n a, j * n b, 0);add((j - 1) * n b, j * n a, 0);}}for(int i 0; i k; i ) add(i * n t, (i 1) * n t, 0);dijkstra(s);printf(%d\n, dist[n * k t]);return 0;
}
1解释数据2≤n≤10^4,1≤m≤10^5,0≤k≤10,0≤s, t, a, bn, a ! b, 0≤c≤10^3
本来数据最大值是m双向边开两倍就可以但是这里是分层建图最多有十层所以要再乘以十
2初始化h数组
3、加边下面的是分层建图
建图从0到k层建k1张图 各层之间从上到下建边花费为0 为防止使用小于k次权力就到达终点在每层的终点间建花费为0的边连起来
4、dijkstra堆优化版的模板
5、答案输出到k层的终点为答案
