C++14(g++5.4) 解法, 执行用时: 378ms, 内存消耗: 12132K, 提交时间: 2020-06-17 09:12:40

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int MX=59;
struct node{
    int u,v,val;
    bool operator<(const node &a)const{
        return val<a.val;
    }
}t[159];
vector<int> vec[MX];
int n,m,k;

struct Node{
    int i,j,k;
};
int ans,dis[59][159][159],vis[59][159][159];
void work(int fr){
    queue<Node> que;
    que.push({1,0,0});
    memset(dis,inf,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[1][0][0]=0;
    vis[1][0][0]=1;
    while( !que.empty() ){
        Node temp=que.front();
        que.pop();
        int ii=temp.i,jj=temp.j,kk=temp.k;
        vis[ii][jj][kk]=0;
        for( int i=0 ; i<vec[ii].size() ; i++ ){
            int num=vec[ii][i];
            int son=(t[num].u==ii?t[num].v:t[num].u);
            int val=t[num].val;
            if( num<=fr ){
                if( jj<fr && dis[son][jj+1][kk]>dis[ii][jj][kk]+t[jj+1].val ){
                    dis[son][jj+1][kk]=dis[ii][jj][kk]+t[jj+1].val;
                    if( !vis[son][jj+1][kk] ){
                        vis[son][jj+1][kk]=1;
                        que.push({son,jj+1,kk});
                    }
                }
            }
            else{
                if( dis[son][jj][kk]>dis[ii][jj][kk]+val ){
                    dis[son][jj][kk]=dis[ii][jj][kk]+val;
                    if( !vis[son][jj][kk] ){
                        vis[son][jj][kk]=1;
                        que.push({son,jj,kk});
                    }
                }
                if( kk<k && jj<fr && dis[son][jj+1][kk+1]>dis[ii][jj][kk]+t[jj+1].val ){
                    dis[son][jj+1][kk+1]=dis[ii][jj][kk]+t[jj+1].val;
                    if( !vis[son][jj+1][kk+1] ){
                        vis[son][jj+1][kk+1]=1;
                        que.push({son,jj+1,kk+1});
                    }
                }
            }
        }
    }
    for( int i=1 ; i<=k ; i++ )
        ans=min(ans,dis[n][fr][i]);
}

int main()
{
//    freopen("input.txt","r",stdin);
    scanf("%d %d %d",&n,&m,&k);
    for( int i=1 ; i<=m ; i++ )
        scanf("%d %d %d",&t[i].u,&t[i].v,&t[i].val);
    sort(t+1,t+1+m);
    for( int i=1 ; i<=m ; i++ ){
        vec[t[i].u].push_back(i);
        vec[t[i].v].push_back(i);
    }
    ans=inf;
    for( int i=1 ; i<=m ; i++ )
        work(i);
    printf("%d\n",ans);
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 264ms, 内存消耗: 2384K, 提交时间: 2023-06-11 21:56:16

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N=60,M=160,INF=0x3f3f3f3f;
int n,m,K,ans;
int dist[N][M][25],vis[N][M][25];
struct Edge{
    int u,v,w;
    bool operator<(const Edge& b) const {return w<b.w;}
}edge[M];
vector<int> mm[N];
void spfa(int sum) {
    memset(dist,0x3f,sizeof dist);
    memset(vis,0,sizeof vis);
    queue<vector<int>> q;
    q.push({1,0,0});
    dist[1][0][0]=0;
    while(!q.empty()) {
        auto t=q.front();q.pop();
        int u=t[0],l=t[1],k=t[2];
        vis[u][l][k]=0;
        for(int i=0;i<mm[u].size();i++) {
            int s=mm[u][i];
            int v=(u==edge[s].u?edge[s].v:edge[s].u);
            if(s<=sum) {
                if(dist[v][l+1][k]>dist[u][l][k]+edge[l+1].w && l<sum) {
                    dist[v][l+1][k]=dist[u][l][k]+edge[l+1].w;
                    if(!vis[v][l+1][k]) {
                        vis[v][l+1][k]=1;
                        q.push({v,l+1,k});
                    }
                }
            }else{
                if(dist[v][l][k]>dist[u][l][k]+edge[s].w) {
                    dist[v][l][k]=dist[u][l][k]+edge[s].w;
                    if(!vis[v][l][k]) {
                        vis[v][l][k]=1;
                        q.push({v,l,k});
                    }
                }
                if(dist[v][l+1][k+1]>dist[u][l][k]+edge[l+1].w && l<sum && k<K) {
                    dist[v][l+1][k+1]=dist[u][l][k]+edge[l+1].w;
                    if(!vis[v][l+1][k+1]) {
                        vis[v][l+1][k+1]=1;
                        q.push({v,l+1,k+1});
                    }
                }
            }
        }
    }
    for(int i=0;i<=K;i++) ans=min(ans,dist[n][sum][i]);
}
int main() {
    scanf("%d%d%d",&n,&m,&K);
    for(int i=1;i<=m;i++) scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
    sort(edge+1,edge+m+1);
    for(int i=1;i<=m;i++) {
        mm[edge[i].u].push_back(i);
        mm[edge[i].v].push_back(i);
    }
    ans=INF;
    for(int i=0;i<=m;i++)
        spfa(i);
    printf("%d\n",ans);
    return 0;
}