[BZOJ 2763] flight route - layered map

BZOJ 2763
flight path

Use this question to explain the use of hierarchical chart:
When solving some graph theory problems, if there are some modified operations, such as allowing free k times in such problems, it is obvious that running the shortest path in the first level graph will cause problems, so we think of a concept of hierarchical graph

If we abstract free k-times into creating k-graphs, we will get free k-times to the next level [edge weight is 0]. This way, running the shortest path again can solve the problem

#include<bits/stdc++.h>
using namespace std;

#define N 10005
#define Dist p.dist
#define Node p.node
#define Free p.free
#define Layer p.free+1
#define ToNode edge[Node][i]

int dis[15][N],n,m,w,s,e,minx=INT_MAX;          //The first dimension of the two two-dimensional arrays is the number of layers, and the second dimension is dis or vis in the current layer
bool vis[15][N];

struct EdgeType{
    int to,cost;
};
struct LineType{        //Priority queues in Dijkstra
    int dist,node,free;             //dist storage minimum distance, node node table, free times
    bool operator < (const LineType &x) const{
        return x.dist<dist;
    }
};

vector <EdgeType> edge[N];          //Using adjacency table to save graph
inline int Read()
{
    int num=0,f=1;
    char t=getchar();
    while (t<'0'||t>'9') f=t=='-'?-1:1,t=getchar();
    while (t>='0'&&t<='9') num=num*10+t-'0',t=getchar();
    return num*f;
}
void Dijkstra(int s)
{
    priority_queue <LineType> line;
    memset(dis,0x7f,sizeof(dis));
    dis[1][s]=0;
    line.push(LineType{0,s,0});
    while (!line.empty())               //Ordinary dijkstra runs to one side, but it's OK to add "if it's still free, run to the next level"
    {
        LineType p=line.top();line.pop();vis[Layer][Node]=1;
        for (int i=0; i<edge[Node].size(); i++) if (dis[Layer][ToNode.to] >= Dist+ToNode.cost)
        {
            dis[Layer][ToNode.to]=Dist+ToNode.cost;
            if (ToNode.to==e) minx=minx>Dist+ToNode.cost?Dist+ToNode.cost:minx;
            if (!vis[Layer][ToNode.to]) line.push(LineType{Dist+ToNode.cost,ToNode.to,Free});
        }
        if (Free < w)
        {
            for (int i=0; i<edge[Node].size(); i++) if (dis[Layer+1][ToNode.to] >= Dist)
            {
                dis[Layer+1][ToNode.to]=Dist;
                if (ToNode.to==e) minx=minx>Dist?Dist:minx;
                if (!vis[Layer+1][ToNode.to]) line.push(LineType{Dist,ToNode.to,Free+1});
            }
        }
    }   
}
/*
Error logging:
1st: The idea is totally confused. dis only has one layer, that is, it operates in one layer, which will obviously cause confusion and fail to achieve the effect of layering
2nd: Similarly, there is only one tier of vis, and then there will be problems when the senior level judges whether to access the update
3rd: The output is directly based on the w+1 layer. If the output is less than w times, for example, if there is a side with s --- > e directly, it will be at dis[2][e]=0, so minx records the minimum value 
*/ 
int main()
{
    n=Read(),m=Read(),w=Read(),s=Read(),e=Read();
    for (int i=1; i<=m; i++) 
    {
        int f=Read(),t=Read(),v=Read();
        edge[f].push_back((EdgeType){t,v});
        edge[t].push_back((EdgeType){f,v});
    }
    Dijkstra(s);
    cout << minx; 
}

Tags: less

Posted on Sat, 02 May 2020 17:16:36 -0700 by alco19357