https://cn.vjudge.net/problem/12427/origin
题意：求1到N第K + 1大条边权最小的路径
首先想到dp递推，dp[x][y]表示到x这个点经过y条免费边的最小值。
直接借助SPFA递推即可
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Scl(x) scanf("%lld",&x);
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x);
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second
typedef vector<int> VI;
const double eps = 1e-;
const int maxn = ;
const int maxm = ;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + ;
int N,M,tmp,K;
struct Edge{
int v,w,next;
}edge[maxm * ];
int head[maxn],tot;
void init(){
Mem(head,-);
tot = ;
}
void add(int u,int v,int w){
edge[tot].v = v;
edge[tot].w = w;
edge[tot].next = head[u];
head[u] = tot++;
}
bool vis[maxn][maxn];
int dp[maxn][maxn]; // 到达i经过p条免费边最大值
struct Node{
int p,x,cost;
Node(int x = ,int p = ,int cost = ):x(x),p(p),cost(cost) {}
};
void SPFA(){
queue<Node>Q;
Q.push(Node(,,));
while(!Q.empty()){
Node u = Q.front(); Q.pop();
vis[u.x][u.p] = ;
for(int i = head[u.x];~i;i = edge[i].next){
int v = edge[i].v;
if(dp[v][u.p] > max(dp[u.x][u.p],edge[i].w)){
dp[v][u.p] = max(dp[u.x][u.p],edge[i].w);
if(!vis[v][u.p]){
vis[v][u.p] = ;
Q.push(Node(v,u.p,dp[v][u.p]));
}
}
if(u.p < K && dp[v][u.p + ] > dp[u.x][u.p]){
dp[v][u.p + ] = dp[u.x][u.p];
if(!vis[v][u.p + ]){
vis[v][u.p + ] = ;
Q.push(Node(v,u.p + ,dp[v][u.p + ]));
}
}
}
}
}
int main()
{
scanf("%d%d%d",&N,&M,&K);
init();
For(i,,M){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w); add(v,u,w);
}
memset(dp,0x3f,sizeof(dp));
dp[][] = ;
SPFA();
int ans = INF;
_For(i,K,){
ans = min(ans,dp[N][i]);
}
if(ans == INF) Pri(-);
else Pri(ans);
#ifdef VSCode
system("pause");
#endif
return ;
}
SPFA
第二个思想是二分答案，将大于这个答案的边权变为0，小于这个答案的边权变为1，直接跑1到N的最短路进行check
对于01图的最短路有一个技巧是用双端队列，类似BFS的方法跑，将权值为1的边进入的点加到队尾，权值0到达的点加到队尾即可。
#include <map>
#include <set>
#include <deque>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Scl(x) scanf("%lld",&x);
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x);
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second
typedef vector<int> VI;
const double eps = 1e-;
const int maxn = ;
const int maxm = ;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + ;
int N,M,tmp,K;
struct Edge{
int v,w,next;
}edge[maxm * ];
int head[maxn],tot;
void init(){
Mem(head,-);
tot = ;
}
void add(int u,int v,int w){
edge[tot].v = v;
edge[tot].w = w;
edge[tot].next = head[u];
head[u] = tot++;
}
bool vis[maxn];
int dis[maxn];
bool check(int x){
deque<int>Q;
Q.push_back();
Mem(vis,);
Mem(dis,0x3f);
dis[] = ;vis[] = ;
while(!Q.empty()){
int u = Q.front(); Q.pop_front();
if(u == N) return dis[u] <= K;
for(int i = head[u]; ~i; i = edge[i].next){
int v = edge[i].v; int w = edge[i].w;
if(w <= x){
dis[v] = min(dis[v],dis[u]);
if(!vis[v]) Q.push_front(v);
}
else{
dis[v] = min(dis[v], + dis[u]);
if(!vis[v]) Q.push_back(v);
}
vis[v] = ;
}
}
return false;
}
int solve(int r){
int l = ;
int ans = -;
while(l <= r){
int m = (l + r) >> ;
if(check(m)){
ans = m;
r = m - ;
}else{
l = m + ;
}
}
return ans;
}
int main()
{
int MAX = ;
scanf("%d%d%d",&N,&M,&K);
init();
For(i,,M){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
MAX = max(MAX,w);
add(u,v,w); add(v,u,w);
}
Pri(solve(MAX));
#ifdef VSCode
system("pause");
#endif
return ;
}