POJ-3662

在 $n$ 个点， $p$ 条边的无向图上求出一条从 $1$ 到 $n$ 的路径，使路径上第 $k+1$ 大的边权尽量小。

$0\le k\le n\le 1000,1\le p\le 10000$

思路

仿照动态规划的思想。定义 $dp[u][x]$ 表示从 $1$ 到 $u$ 的路径上免费升级了 $x$ 条边后最大的边权。

那么对于每一条边 $(u,v,w)$ ，可以考虑是否免费升级该边。

若免费升级，那么用 $dp[u][x]$ 来更新 $dp[v][x+1]$ 的最小值。

若不升级，那么用 $\max(dp[u][x],w)$ 来更新 $dp[v][x]$ 的最小值。

这样的状态转移显然是具有后效性的，所以考虑利用迭代思想，借助 SPFA 进行动态规划，直至所有状态收敛。

这样的话，将每个状态 $(u,x)$ 看成一个节点，于是就是一个 $nk$ 个点， $pk$ 条边的无向图。

时间复杂度 $O(tnp)$ ，其中 $t$ 为常数。

代码

#include<bits/stdc++.h>
#define N 1010
#define M 10010
#define INF 0x3f3f3f3f

using namespace std;

inline int read() {
    int w=1,x=0;
    char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return w*x;
}

int n,p,k,ans=INF;

int head[N],tot=0;
struct graph{
    int v,w,next;
}edge[M<<1];
void add(int u,int v,int w) {edge[++tot].v=v,edge[tot].w=w,edge[tot].next=head[u],head[u]=tot;}

int dp[N][N];
bool vh[N][N];
void SPFA(int s) {
    memset(dp,0x3f,sizeof(dp));
    queue<pair<int,int> > q;
    q.push(make_pair(s,0));
    vh[s][0]=true;
    dp[s][0]=0;
    while(!q.empty()) {
        int u=q.front().first,x=q.front().second;
        vh[u][x]=false;
        q.pop();
        for(int i=head[u];i;i=edge[i].next) {
            int v=edge[i].v,w=edge[i].w;
            if(dp[v][x]>max(dp[u][x],w)) {
                dp[v][x]=max(dp[u][x],w);
                if(!vh[v][x]) {
                    q.push(make_pair(v,x));
                    vh[v][x]=true;
                }
            }
            if(x+1<=k&&dp[v][x+1]>dp[u][x]) {
                dp[v][x+1]=dp[u][x];
                if(!vh[v][x+1]) {
                    q.push(make_pair(v,x+1));
                    vh[v][x+1]=true;
                }
            }
        }
    }
}

int main() {
    n=read(),p=read(),k=read();
    for(int i=1;i<=p;i++) {
        int u=read(),v=read(),w=read();
        add(u,v,w);
        add(v,u,w);
    }    
    SPFA(1);
    for(int i=0;i<=k;i++) ans=min(ans,dp[n][i]);
    ans==INF?printf("-1\n"):printf("%d\n",ans);
    system("pause");
    return 0;
}