计蒜客 Magical Girl Haze ——dijkstra+优先队列

There are NN cities in the country, and MM directional roads from uu to v(1\le u, v\le n)v(1≤u,v≤n). Every road has a distance c_ic
i
​ . Haze is a Magical Girl that lives in City 11, she can choose no more than KK roads and make their distances become 00. Now she wants to go to City NN, please help her calculate the minimum distance.

Input
The first line has one integer T(1 \le T\le 5)T(1≤T≤5), then following TT cases.

For each test case, the first line has three integers N, MN,M and KK.

Then the following MM lines each line has three integers, describe a road, U_i, V_i, C_iU
i
​ ,V
i
​ ,C
i
​ . There might be multiple edges between uu and vv.

It is guaranteed that N \le 100000, M \le 200000, K \le 10N≤100000,M≤200000,K≤10,
0 \le C_i \le 1e90≤C
i
​ ≤1e9. There is at least one path between City 11 and City NN.

Output
For each test case, print the minimum distance.

样例输入 复制
1
5 6 1
1 2 2
1 3 4
2 4 3
3 4 1
3 5 6
4 5 2
样例输出 复制
3
题目来源
ACM-ICPC 2018 南京赛区网络预赛

当时比赛的时候用dp+dij的，但是由于我处理顺序写的比较失败这道题卡了好久，还是队友写了个暴力才过的。
只需要用一个dij就好了，优先队列重载一下操作符就像上次那道做公交车换乘的题目一样，真是失误

#include<stdio.h>
#include<iostream>
#include<queue>
using namespace std;
#define ll long long
const int maxn=1e5+5;
const ll inf=1e17;
struct edge
{
    int to,next;
    ll val;
}e[maxn*2];
int head[maxn],cnt;
void add(int x,int y,ll w)
{
    e[cnt].to=y;
    e[cnt].val=w;
    e[cnt].next=head[x];
    head[x]=cnt++;
}
ll dist[maxn][11],vis[maxn][11];
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
    {
        if(dis==a.dis)
            return num>a.num;
        return dis>a.dis;
    }
};
int n,m,k;
void dijkstra()
{
    priority_queue<node>Q;
    Q.push(node(0,0,1));
    while(!Q.empty())
    {
        node v=Q.top();
        Q.pop();
        if(vis[v.pos][v.num])
            continue;
        vis[v.pos][v.num]=1;
        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].val)
            {
                dist[ne][v.num]=v.dis+e[i].val;
                Q.push(node(dist[ne][v.num],v.num,ne));
            }
            if(v.num<k&&v.dis<dist[ne][v.num+1])
            {
                dist[ne][v.num+1]=v.dis;
                Q.push(node(v.dis,v.num+1,ne));
            }
        }
    }
}
void init()
{
    for(int i=0;i<maxn;i++)
    {
        head[i]=-1;
        for(int j=0;j<=10;j++)
            dist[i][j]=inf,vis[i][j]=0;
    }
    cnt=0;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&k);
        int x,y;
        ll val;
        init();
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%lld",&x,&y,&val);
            add(x,y,val);
        }
        for(int i=0;i<=k;i++)
            dist[1][0]=0;
        dijkstra();
        ll ans=inf;
        for(int i=0;i<=k;i++)
            ans=min(ans,dist[n][i]);
        printf("%lld\n",ans);

    }
    return 0;
}