裸地分层图最短路
培训的时候考到过
但是……
我考试的时候写了个基本没有的树状数组优化。然后顺利的被卡到了70分（裸的spfa都有80分qwq）
伤心
然后今天又重新拿堆优化dij搞了一波。一发ac真开心qwq
#include#include #include #include #include using std::min;using std::priority_queue;const int maxn=20100;int dis[maxn][21],head[maxn],tail;bool Get[maxn][21];int n,m,k;struct node{ int point; int weight; int nxt;};struct Data//优先队列使用的结构体{ int p,k; int val; Data (int a=0,int b=0,int c=0){ p=a,k=b,val=c; } bool operator < (const Data &A)const { return val>A.val; }};node line[101000];int read(){ int res=0;char c=getchar(); while(c>'9'||c<'0') c=getchar(); while(c>='0'&&c<='9') { res=res*10+c-'0'; c=getchar(); } return res;}void add(int x,int y,int z){ line[++tail].point=y; line[tail].nxt=head[x]; line[tail].weight=z; head[x]=tail;}void bfs(){ priority_queue q; memset(dis,127,sizeof(dis)); dis[1][0]=0; q.push(Data(1,0,0));//起点 int tot=0; while(!q.empty()) { Data pas=q.top();q.pop(); //printf("\t%d\t%d\t%d\n",pas.p,pas.k,pas.val); while(Get[pas.p][pas.k])//这个状态已经到达了 { pas=q.top(); q.pop(); } int P=pas.p,K=pas.k; Get[P][K]=true; if(P==n)//终点状态 { printf("%d",pas.val); break; } for(int i=head[P];i;i=line[i].nxt) { int v=line[i].point; if(K+1<=k&&dis[v][K+1]>dis[P][K])//使用边权无效化 { dis[v][K+1]=dis[P][K]; Data nxt(v,K+1,dis[v][K+1]); q.push(nxt); } if(dis[v][K]>dis[P][K]+line[i].weight)//不消除边权 { dis[v][K]=dis[P][K]+line[i].weight; Data nxt(v,K,dis[v][K]); q.push(nxt); } } }}int main(){ //n=read(),m=read(),k=read(); scanf("%d%d%d",&n,&m,&k); int a,b,c; for(int i=1;i<=m;i++) { //int a=read(),b=read(),c=read(); scanf("%d%d%d",&a,&b,&c); add(a,b,c);add(b,a,c); } bfs();}/*5 6 11 2 21 3 42 4 33 4 13 5 64 5 2*/