题意：同飞行路线
思路：这个题竟然不仅能卡点spfa，还能卡掉一维的dij，（出题人好优秀啊），搬运了一份二维的分成图dij，感谢神犇（传送门）
代码：
#include<bits/stdc++.h> using namespace std; typedef long long LL; inline int read() { int x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } struct node { int next,to,val; }edge[100005]; int head[10005],cnt; struct Node { int to,val,sum; friend bool operator<(Node a,Node b){return a.val>b.val;} }; void addedge(int u,int v,int w) { edge[++cnt].next=head[u]; edge[cnt].to=v; edge[cnt].val=w; head[u]=cnt; } void add(int u,int v,int w) { addedge(u,v,w); addedge(v,u,w); } void init() { cnt=0; memset(head,-1,sizeof(head)); } int dis[10005][25],vis[10005][25]; int k; void dijsktra(int s) { priority_queue<Node>que; memset(dis,127/3,sizeof(dis)); dis[s][0]=0; que.push((Node){s,0,0}); while(!que.empty()){ Node x=que.top();que.pop(); if(vis[x.to][x.sum])continue; vis[x.to][x.sum]=1; for(int i=head[x.to];i!=-1;i=edge[i].next){ int y=edge[i].to; if(dis[y][x.sum+1]>dis[x.to][x.sum]&&x.sum+1<=k){ dis[y][x.sum+1]=dis[x.to][x.sum]; que.push((Node){y,dis[y][x.sum+1],x.sum+1}); } if(dis[y][x.sum]>dis[x.to][x.sum]+edge[i].val){ dis[y][x.sum]=dis[x.to][x.sum]+edge[i].val; que.push((Node){y,dis[y][x.sum],x.sum}); } } } return ; } int main() { init(); int n,m; scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=m;i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w); } dijsktra(1); cout<<dis[n][k]<<endl; return 0; }