欢迎访问 My Luogu Space。
【题目描述】
已给定一个 (N) 个点 (M) 条边的无向图，点编号为 (1) 到 (N) ，第 (i) 条边为 ((u_i, v_i)) ，权值为 (w_i) 。你可以进行一次操作，使得任意一条边的权值变成任意非负整数。要求进行尽量少的操作次数，使得点 (1) 到点 (N) 的最短路径长度变成 (c) 。
题目保证，(c) 小于在未进行任何操作之前的原图中 (1) 到 (N) 的最短路长度。
【 输入输出格式】
输入格式：
第一行三个整数，(N)，(M) 和 (c)，接下来M行，每行一条边的信息(u_i)，(v_i) 和 (w_i)，第 (i) 行的表述第 (i) 条边的信息。保证不会有自环存在，对于不同的 (i) 和 (j)，((u_i, v_i)) 不同于 ((u_j, v_j))。
输出格式：
一行一个整数，要进行最少多少次操作才能使得最短路长度变为 (c) 。
【输入输出样例】
输入样例：
3 3 3
1 2 3
2 3 3
1 3 8
输出样例：
1
【提示】
【样例说明】
将边 (1) ，(3) 的权值修改为 (2) 就可以了。
【数据范围】
(N≤100)
(M≤1000)
(0≤c≤100000)
(0≤wi≤10000)
(30\%) 数据满足 (M≤20)
【标签】
图论，最短路。
【分析】
类似于DP的单源最短路。
基本想法：
根据题意，可以贪心地想到：将尽可能少的边缩到长度为 (0) ，若此时最短路小于 (c) ，说明能够满足达到 (c) 。
改进：
设计状态 (Dis[i][j]) 表示从 (1) 出发到达 (i) ，已经有 (j) 条边被缩为 (0) 。跑最短路算法。
每次更新最短路时，分两种情况：
- 直接到达目标点，最短路长度不增加（相当于通过一条长度为 (0) 的路径）。当前缩的路的数量(+1)；
- 通过路径到达目标点，同正常的最短路写法；
算法结束时从 (Dis[n][1]) 到 (Dis[n][m]) 依次判断是否小于 (c)，第一个小于 (c) 的 (j)就是答案。
【代码】
[C++]
#include <bits/stdc++.h>
#define P(a, b, c) (P){a, b, c}
using namespace std;
const int INF = 0x3f3f3f3f;
struct T{int w, to;}E[2005];
struct P{
int dis, cnt, id;
bool operator<(const P &T)const{
return dis > T.dis;
}
};
int Dis[105][1005], n, m, c, Hed[105], Nex[2005], ct = 1;
bool F[105][1005];
void Add(int a, int b, int w){
E[++ct].to = b, E[ct].w = w, Nex[ct] = Hed[a], Hed[a] = ct;
E[++ct].to = a, E[ct].w = w, Nex[ct] = Hed[b], Hed[b] = ct;
}
void Dijkstra(){
priority_queue<P> Q; Q.push(P(0, 0, 1));
memset(Dis, INF, sizeof Dis);
Dis[1][0] = 0; P k;
while(!Q.empty()){
k = Q.top(); Q.pop();
F[k.id][k.cnt] = 1;
for(int i=Hed[k.id]; i; i=Nex[i]){
if(Dis[E[i].to][k.cnt] > Dis[k.id][k.cnt]+E[i].w){
Dis[E[i].to][k.cnt] = Dis[k.id][k.cnt]+E[i].w;
Q.push(P(Dis[E[i].to][k.cnt], k.cnt, E[i].to));
}
if(k.cnt<m && Dis[E[i].to][k.cnt+1]>Dis[k.id][k.cnt]){
Dis[E[i].to][k.cnt+1] = Dis[k.id][k.cnt];
Q.push(P(Dis[E[i].to][k.cnt+1], k.cnt+1, E[i].to));
}
}
while(!Q.empty() && F[Q.top().id][Q.top().cnt]) Q.pop();
}
}
int main(){
int a, b, d;
scanf("%d%d%d", &n, &m, &c);
for(int i=1; i<=m; ++i){
scanf("%d%d%d", &a, &b, &d);
Add(a, b, d);
}
Dijkstra();
for(int i=0; i<=m; ++i){
if(Dis[n][i] <= c)
printf("%d", i), exit(0);
}
return 0;
}