DP/二分 + 最短路

方法1 DP

用d[x][y]表示从1号节点到达x号节点,途中经过了y条免费电缆时,经过的路上最贵的电缆花费最小是多少.
假设有一条边从 x 到 v ，权值为 w ，则我们可以：

• 用 max(dp[x][y],w) 更新 dp[v][y] ,这个表示不在电缆 x-v 使用免费服务。
• 用 dp[x][y] 更新 dp[v][p+1] ,表示在电缆 x-v 上使用免费服务

由于这个dp有后效性，不能用dij，采用spfa不断迭代更新。

#include <bits/stdc++.h>//缩短代码用了万能头，poj不允许这样
using namespace std;
const int N = 1e3 + 10;
const int inf = 0x3f3f3f3f;
int n, pp, k;
struct E{
	int to, next, w;
}edge[20 * N];
int tot;
int head[N];
bool vis[N][N];
int dp[N][N];
void addedge(int from, int to, int w)
{
	edge[++tot].to = to;
	edge[tot].w = w;
	edge[tot].next = head[from];
	head[from] = tot;
}
typedef pair<int, int> P;
queue<P> q;
void spfa()
{
	memset(dp, inf, sizeof(dp));
	dp[1][0] = 0;
	vis[1][0] = true;
	q.push(P(1, 0));
	while (!q.empty())
	{
		P u = q.front();
		q.pop();
		int x = u.first, p = u.second;
		vis[x][p] = false;
		for (int i = head[x]; i != -1; i = edge[i].next)
		{
			int v = edge[i].to, w = edge[i].w;
			if (dp[v][p]>max(dp[x][p], w))
			{
				dp[v][p] = max(dp[x][p], w);
				if (!vis[v][p])
				{
					vis[v][p] = true;
					q.push(P(v, p));
				}
			}
			if (p<k&&dp[v][p + 1]>dp[x][p])
			{
				dp[v][p + 1] = dp[x][p];
				if (!vis[v][p + 1])
				{
					vis[v][p + 1] = true;
					q.push(P(v, p + 1));
				}
			}
		}
	}

}
int main()
{
	scanf("%d%d%d", &n, &pp, &k);
	memset(head, -1, sizeof(head));
	while (pp--)
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		addedge(u, v, w);
		addedge(v, u, w);
	}
	spfa();
	int ans = inf;
	for (int i = 0; i <= k; i++)
	{
		ans = min(ans, dp[n][i]);
	}
	printf("%d\n", ans == inf ? -1 : ans);
	return 0;
}

方法2 二分

显然答案具有单调性。二分答案，假设答案为mid，我们将边权大于等于mid的边的边权设为1，表示免费服务的边，即可以理解为使用了一次免费服务。小于mid的边权设为0，表示不免费，没有使用免费服务。然后我们跑一便最短路，看最短路径是否小于等于K，小于等于则mid是满足的，我们可以缩小mid,继续二分答案。

#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>
using namespace std;
const int N = 1e3 + 10;
const int inf = 0x3f3f3f3f;
int n, pp, k;
struct E{
	int to, next, w;
}edge[20 * N];
int tot;
int head[N];
bool vis[N];
int dis[N];
void addedge(int from, int to, int w)
{
	edge[++tot].to = to;
	edge[tot].w = w;
	edge[tot].next = head[from];
	head[from] = tot;
}
typedef pair<int, int> P;
queue<int> q;
int spfa(int mid)
{
	while (!q.empty()) q.pop();
	memset(vis, false, sizeof(vis));
	memset(dis, inf, sizeof(dis));
	dis[1] = 0;
	vis[1] = true;
	q.push(1);
	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		vis[u] = false;
		for (int i = head[u]; i != -1; i = edge[i].next)
		{
			int v = edge[i].to;
			int w = (edge[i].w >= mid);
			if (dis[v] > dis[u]+ w)
			{
				dis[v] = dis[u] + w;
				if (!vis[v])
				{
					vis[v]= true;
					q.push(v);
				}
			}
		}
	}
	return dis[n] <= k;
}
int main()
{
	scanf("%d%d%d", &n, &pp, &k);
	memset(head, -1, sizeof(head));
	int l = 0;
	while (pp--)
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		addedge(u, v, w);
		addedge(v, u, w);
	}
	int r = 1e7;
	while (l < r)
	{
		int mid = (l+r+1) >> 1;
		if (!spfa(mid)) l = mid;
		else r = mid - 1;
	}
	printf("%d\n", l >=1e7 ? -1 : l);
	return 0;
}