建图优化

· · 个人记录

分层图

首先讲讲如何分辨是不是分层图优化？

  1. 题目里面出现了一些特殊的位置是有传送等功能。
  2. 题目中对一些点流量限制。

例题

分层图的实现逻辑（基于例题）

我们可以知道例题中，特殊的点是全部点，不过题目有次数限制，我们不用分层图十分复杂。

分层图嘛，顾名思义就是多个图叠在一起了，在这题中有k次免费，我们就建k层图，每个结点对下一层图中自己相邻的结点连单向边，不用代价。

接下来我们就可以直接在这么帅气的图上面跑一次最短路即可。

题目里限制了k次免费，我们在这个图上面跑最短路，最多用k免费，因为我们跑最短路时，代码走过去这个点以后就不能回去了，就类似一个3d的图，到了下一层就不能回去了。

最后输出的答案就是，k层图中结点n的最小值。（因题目而异，有可能是必须走完k次的）

#include<bits/stdc++.h>
using namespace std;
const int N=10005;
const int K=15;
const int INF=2147483647;
struct node{
    int u,d;
    bool operator<(const node&a)const{
        return d>a.d;
    }
};
vector<pair<int,int>> g[N*(K+1)];
int dis[N*(K+1)];
bool vis[N*(K+1)];
int n,m,k,s,t;
int main(){
    cin>>n>>m>>k>>s>>t;
    for(int i=0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        for(int j=0;j<=k;j++){
            int uu=j*n+u,vv=j*n+v;
            g[uu].push_back({vv,w});
            g[vv].push_back({uu,w});
        }
        for(int j=0;j<k;j++){
            int uu=j*n+u,vv=(j+1)*n+v;
            g[uu].push_back({vv,0});
            uu=j*n+v,vv=(j+1)*n+u;
            g[uu].push_back({vv,0});
        }
    }
    for(int i=0;i<=k*n+n;i++)dis[i]=INF;
    dis[s]=0;
    priority_queue<node> q;
    q.push({s,0});
    while(!q.empty()){
        int u=q.top().u;
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(auto e:g[u]){
            int v=e.first,w=e.second;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push({v,dis[v]});
            }
        }
    }
    int ans=INF;
    for(int i=0;i<=k;i++)ans=min(ans,dis[i*n+t]);
    cout<<ans;
    return 0;
}

隐式建图

例题

给定两个不同的质数 start 和 end（都是4位数），每次操作可以改变一个数字（0\to9），但改变后的数字必须是4位数且仍是质数。 求从 start 到 end 的最少变换次数。如果无法到达，返回 -1。

很明显这道题目,无法把所有的边都建出来,我们可以不预先存储所有边，而是在djikstra时动态生成邻居连起就行了。

代码不放了

作者偷懒