题意：

有N个结点，由M条双向边连接，每条边有权值。可以把最多k条边的权值改为0。问从1到N的最短路为多少。其中$1 <= N <= 10000$，$1 <= K <= 20$。

思路：

法一：拆点。

把图分为k层，层与层之间的路权值为0，每次走上一条权值为0的边相当于在层之间走。

注意数组开的大小。

如图：

法二：DP思想。

$dis[i][j]$：到第i个结点把j条边权值改为0的最短路。

根据松弛有$dis[p][j]=min(dis[i][j]+w(i,p))$，还有一种转移是层与层之间，即权值为0的情况，$dis[p][j+1]=min(dis[i][j]+0)$。

复杂度为$O(nklog(nk))$。

代码：

法一：

typedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
int top;
int head[500010];
struct edge
{
    int to;
    ll cost;
    int next;
}eg[5000010];
void add(int a,int b,ll c)
{
    eg[top].cost=c;
    eg[top].to=b;
    eg[top].next=head[a];
    head[a]=top++;
}
typedef pair<ll,int>p;
ll dis[500010];
int n;
void dijkstra()
{
    fill(dis+1,dis+n+1,INF);
    dis[1]=0;
    priority_queue<p,vector<p>,greater<p> >q;
    q.push(p(0,1));
    while(!q.empty())
    {
        p temp=q.top();
        q.pop();
        ll w=temp.first;
        int id=temp.second;
        if(w>dis[id])continue;
        for(int i=head[id];i!=-1;i=eg[i].next)
        {
            edge &e=eg[i];
            if(w+e.cost<dis[e.to])
            {
                dis[e.to]=w+e.cost;
                q.push(p(dis[e.to],e.to));
            }
        }
    }
    /*for(int i=1;i<=n;i++)
        printf("%lld ",dis[i]);
    printf("\n");*/
}
int main()
{
    int m,k,x,y;
    ll w;
    scanf("%d%d%d",&n,&m,&k);
    top=0;
    memset(head,-1,sizeof(head));
    while(m--)
    {
        scanf("%d%d%lld",&x,&y,&w);
        for(int i=0;i<=k;i++)
        {
            add(x+i*n,y+i*n,w);
            add(y+i*n,x+i*n,w);
            if(i!=k)
            {
                add(x+i*n,y+(i+1)*n,0);
                add(y+i*n,x+(i+1)*n,0);
            }
        }
    }
    n=(k+1)*n;
    /*for(int i=1;i<=n;i++)
    {
        for(int j=head[i];j!=-1;j=eg[j].next)
            printf("%d ",eg[j].to);
        printf("\n");
    }*/
    dijkstra();
    printf("%lld\n",dis[n]);
    return 0;
}

法二：

typedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
int top;
int head[10010];
struct edge
{
    int to;
    ll cost;
    int next;
}eg[100010];
void add(int a,int b,ll c)
{
    eg[top].cost=c;
    eg[top].to=b;
    eg[top].next=head[a];
    head[a]=top++;
}
typedef pair<int,int> pp;
typedef pair<ll,pp>p;
ll dis[10010][25];
bool vis[10010][25];
int n;
int k;
void dijkstra()
{
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[1][0]=0;
    priority_queue<p,vector<p>,greater<p> >q;
    q.push(p(0,pp(1,0)));
    while(!q.empty())
    {
        p temp=q.top();
        q.pop();
        ll w=temp.first;
        int id=temp.second.first;
        int cur=temp.second.second;
        if(vis[id][cur])continue;
        vis[id][cur]=true;
        for(int i=head[id];i!=-1;i=eg[i].next)
        {
            edge &e=eg[i];
            if(w+e.cost<dis[e.to][cur])
            {
                dis[e.to][cur]=w+e.cost;
                q.push(p(dis[e.to][cur],pp(e.to,cur)));
            }
            if(cur<k&&w<dis[e.to][cur+1])
            {
                dis[e.to][cur+1]=w;
                q.push(p(dis[e.to][cur+1],pp(e.to,cur+1)));
            }
        }
    }
}
int main()
{
    int m,x,y;
    ll w;
    scanf("%d%d%d",&n,&m,&k);
    top=0;
    memset(head,-1,sizeof(head));
    while(m--)
    {
        scanf("%d%d%lld",&x,&y,&w);
        add(x,y,w);
        add(y,x,w);
    }
    dijkstra();
    printf("%lld\n",dis[n][k]);
    return 0;
}