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

昨天考试分层图最短路用个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;
}