Dijkstra+优先队列 模板

 #include<bits/stdc++.h>
 using namespace std;
 #define ll long long
 const int maxn=1e5+;
 const ll inf=1e17;
 struct node
 {
     ll dis;
     int num,pos;
     node() {}
     node(ll dis,int num,int pos):dis(dis),num(num),pos(pos) {}
     bool operator< (const node& a)const
     {
         return dis>a.dis;
     }
 };
 struct edge
 {
     int to,next;
     ll z;
 } e[maxn*];//双边，无向图，所以乘以2
 int head[maxn],cnt;
 void add(int x,int y,ll w)// w边值
 {
     e[cnt].to=y;
     e[cnt].z=w;
     e[cnt].next=head[x];
     head[x]=cnt++;
 }
 ll dist[maxn][],vis[maxn][];

 int n,m,k;
 void dijkstra()
 {
     priority_queue<node>Q;//优先队列
     Q.push(node(,,));
     while(!Q.empty())
     {
         node v=Q.top();
         Q.pop();
         if(vis[v.pos][v.num])
             continue;
         vis[v.pos][v.num]=;
         for(int i=head[v.pos]; ~i; i=e[i].next)
         {
             int ne=e[i].to;
             if(dist[ne][v.num]>v.dis+e[i].z)
             {
                 dist[ne][v.num]=v.dis+e[i].z;
                 Q.push(node(dist[ne][v.num],v.num,ne));
             }
             if(v.num<k && v.dis<dist[ne][v.num+])
             {
                 dist[ne][v.num+]=v.dis;
                 Q.push(node(v.dis,v.num+,ne));
             }
         }
     }
 }
 void init()//初始化图，有点之间距离为无穷，每个点的标志初始为0，边的条数cnt初始为0
 {
     for(int i=; i<maxn; i++)
     {
         head[i]=-;
         for(int j=; j<=; j++)
             dist[i][j]=inf,vis[i][j]=;
     }
     cnt=;
 }
 int main()
 {
     int t;
     scanf("%d",&t);
     while(t--)
     {
         scanf("%d%d%d",&n,&m,&k);
         int x,y;
         ll z;
         init();
         for(int i=; i<=m; i++)
         {
             scanf("%d%d%lld",&x,&y,&z);
             add(x,y,z);
         }
         dist[][]=;
         dijkstra();
         ll ans=inf;
         for(int i=; i<=k; i++)
             ans=min(ans,dist[n][i]);
         printf("%lld\n",ans);

     }
     return ;
 }

参看原博客：https://blog.****.net/tianyizhicheng/article/month/2018/09