[分层图最短路][学习笔记]
程序员文章站
2022-07-28 17:09:57
昨天考试分层图最短路用个dp暴力水了90分。今天只有10分。。。还是好好来学分层图吧。~~(实际是不想学数据结构2333)~~
一类问题
分层图最短路得经典模板题就是这样 ......
昨天考试分层图最短路用个dp暴力水了90分。今天只有10分。。。还是好好来学分层图吧。(实际是不想学数据结构2333)
一类问题
分层图最短路得经典模板题就是这样
给出一个n个点m条边的无向图,每条边有边权,可以选择最多k条边,把他们的边权变为0。问从s到t的最短路是多少。
解法
一般这类问题k都会比较小。所以可以建k层图。第i层图表示已经把i条边变成0。
然后就是怎么连边。首先在每层图中,u和v之间还是要连边的。那么两层图之间的边呢。为了表示出已经把一条边变为0了,所以要把第i - 1层图中的u向第i层中的v连一条权值为0的边,因为是无向图。所以还要把第i - 1层中的v向第i层中的u连一条权值为0的边。
一些细节
那么怎么来表示这个点是第几层图中的呢??
有一个非常经典的做法。就是把第i层图中的j号点的编号记为i * n +j。这样就可以保证每层图中节点的标号都不一样,并且还可以准确找到每层图的每个节点。
为啥不挂图?
懒
题面
一条道路移动到另一条道路之类的时间,只计算他在这些道路上花费的时间总和。
除此之外,小喵喵还有k个时间暂停器,每个可以使某一条道路的经过时间变为0.
【输入格式】
第1行三个整数n,m,k,表示路口个数,道路的数量,时间暂停器的数量。
第2~m+1行每行三个整数u[i],v[i],c[i],表示u[i]和v[i]之间有一条可以双向通行的道路,通过所需时间为c[i]。
【输出格式】
一个整数,表示小喵喵所需的最短时间。
【样例输入输出】
5 6 1
1 2 2
1 3 4
2 4 3
3 4 1
3 5 6
4 5 2 3
【样例解释】
小喵喵选择从1->3->4->5,并且在1->3的道路上使用时间暂停器。
总耗时为0+1+2=3.
【数据范围】
对于20%的数据,n<=5,m<=10.
对于另外20%的数据,k=0.
对于另外30%的数据,k=1.
对于所有的数据,n<=1000,m<=10000,k<=10,c[i]<=109,保证存在从1号路口到n号路口的路径。注意,可能存在两条道路的起点和终点组成的集合相同,也可能存在起点和终点是相同路口的道路。
代码
/* * @author: wxyww * @date: 2018-12-15 15:10:24 * @last modified time: 2018-12-15 17:27:21 */ #include<cstdio> #include<iostream> #include<queue> #include<cstring> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> using namespace std; typedef long long ll; const int n = 100000 + 100; const ll inf = 1e14; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } struct node { int v,nxt,w; }e[n * 20]; int n,m,k; int head[n],ejs; void add(int u,int v,int w) { e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;e[ejs].w = w; } ll dis[n * 20]; queue<int>q; int vis[n]; void spfa() { q.push(1); while(!q.empty()) { int u = q.front();q.pop(); vis[u] = 0; for(int i = head[u];i;i = e[i].nxt) { int v = e[i].v; if(dis[v] > dis[u] + e[i].w) { dis[v] = dis[u] + e[i].w; if(!vis[v]) { vis[v] = 1; q.push(v); } } } } } int main() { n = read(),m = read(),k = read(); for(int i = 1;i <= m;++i) { int u = read(),v = read(),w = read(); add(u,v,w); add(v,u,w); for(int j = 1;j <= k;++j) { add(j * n + u,j * n + v,w); add(j * n + v,j * n + u,w); add((j - 1) * n + u,j * n + v,0); add((j - 1) * n + v,j * n + u,0); } } for(int i = 0;i <= n * k + n;++i) dis[i] = inf; dis[1] = 0; spfa(); ll ans = dis[n]; for(int i = 0;i <= k;++i) ans = min(ans,dis[i * n + n]); cout<<ans; return 0; }
推荐阅读
-
Python学习笔记--使用matplotlib绘制饼状图
-
算法学习笔记 二叉树和图遍历—深搜 DFS 与广搜 BFS
-
Python学习笔记--使用matplotlib绘制饼状图
-
BZOJ2763: [JLOI2011]飞行路线(分层图 最短路)
-
全网最详细的Python学习笔记,值得收藏
-
[分层图最短路][学习笔记]
-
(浙大-19-夏-数据结构学习笔记+代码)图的遍历+深度优先+广度优先(Graph)
-
安卓开发学习笔记(五):史上最简单且华丽地实现Android Stutio当中Webview控件https/http协议的方法
-
最全面的Python网络爬虫 思维导图总结学习笔记
-
pytorch学习1-张量及基本操作、计算图、自动求导系统(学习笔记)