洛谷P2939 [USACO09FEB]Revamping Trails G

题目

https://www.luogu.com.cn/problem/P2939

思路

分层图最短路的板子题，考虑到是稀疏图，用堆优化的dijkstra算法比较合理。

代码

#include
#include
#include
#include
#define maxn 50010
#define inf 0x3f3f3f3f
using namespace std;
int fst[maxn],nxt[maxn<<1],to[maxn<<1],w[maxn<<1],cnt=0;
int d[maxn][21];
int vis[maxn][21];
struct node{
    int dis,idx,idy;
    bool operator <(const node &t) const{
        return dis>t.dis;
    }
    node(){}
    node(int x,int y,int z){
        dis=x;idx=y;idy=z;
    }
};
void add(int x,int y,int z){
    to[++cnt]=y;
    w[cnt]=z;
    nxt[cnt]=fst[x];
    fst[x]=cnt;
}
int dijkstra(int n,int k){
    int i,j;
    priority_queue q;
    for(i=1;i<=n;++i)
        for(j=0;j<=k;++j)
            vis[i][j]=0;
    for(i=1;i<=n;++i)
        for(j=0;j<=k;++j)
            d[i][j]=inf;
    d[1][k]=0;
    q.push(node(0,1,k));
    while(!q.empty()){
        while(!q.empty()&&vis[q.top().idx][q.top().idy]) q.pop();
        if(q.empty()) break;
        node p=q.top();
        q.pop();
        vis[p.idx][p.idy]=1;
        for(i=fst[p.idx];i;i=nxt[i]){
            if(p.dis+w[i]