欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

[分层图最短路][学习笔记]

程序员文章站 2022-04-22 23:29:41
昨天考试分层图最短路用个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;
}