题目链接：点击打开链接
题意：
给定n个点m条有向边 常数c
下面m行给出边。
修改最少的边的边权使得1->n的最短路长度恰好为c（输入保证1->n存在最短路且最短路权值>c)
思路：
因为是DAG，而且c不大，，所以应该是DAG上的dp，反向建边然后bfs出去。
dp[i][j]表示点i距离终点距离恰好为j时最少需要修改的边数。
初始状态为dp[n][0] = 0, 其他为inf。
从u转移到v，若边权不修改则：
1、dp[v][j+edge.dis] = min(dp[u][j]);
若修改这条边权则方程为：
2、dp[v][j] = min(dp[u][ j-? ] +1);
显然2的转移复杂度就是c*c,这样就太大了。
其实若把最短路修改为恰好为c 和 修改为<=c的答案是一样的，因为c越小答案应该越大，所以我们把题意转换成修改为<=c，
则ans = min(dp[n][ 0->c ])
这样2的方程就能改成dp[v][j] = min( dp[u][j]+1 );
O(1)的转移。
复杂度为O(m*c)
over.
#include <stdio.h>#include <string.h>#include <set> #include <map> #include <algorithm> #include <iostream> #include <vector> #include <string> #include <queue>#include <cmath> template <class T>inline bool rd(T &ret) {char c; int sgn;if (c = getchar(), c == EOF) return 0;while (c != '-' && (c<'0' || c>'9')) c = getchar();sgn = (c == '-') ? -1 : 1;ret = (c == '-') ? 0 : (c – '0');while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c – '0');ret *= sgn;return 1;}template <class T>inline void pt(T x) {if (x <0) {putchar('-');x = -x;}if (x>9) pt(x / 10);putchar(x % 10 + '0');}using namespace std;const int inf = 1e8;const int N = 105;const int M = 100010;struct Edge{int from, to, dis, nex;}edge[1005];int head[N], edgenum;void add(int u, int v, int dis){Edge E = { u, v, dis, head[u] };edge[edgenum] = E;head[u] = edgenum++;}void init(){ memset(head, -1, sizeof head); edgenum = 0; }int n, m, c;int dp[N][M], vis[N];void bfs(){queue<int>q;q.push(n);dp[n][0] = 0;while (!q.empty()){int u = q.front(); q.pop(); vis[u] = 0;for (int i = head[u]; ~i; i = edge[i].nex){int v = edge[i].to;bool ok = false;for (int j = 0; j <= c; j++){if (dp[u][j] == inf)continue;if (dp[v][j] > dp[u][j] + 1){dp[v][j] = dp[u][j] + 1; ok = true;}if (j + edge[i].dis <= c && dp[v][j + edge[i].dis] > dp[u][j]){dp[v][j + edge[i].dis] = dp[u][j]; ok = true;}}if (ok && vis[v] == 0)vis[v] = 1, q.push(v);}}}int main(){int u, v, d;while (cin>>n>>m>>c, n+m+c){init();memset(vis, 0, sizeof vis);for (int i = 1; i <= n; i++)for (int j = 0; j <= c; j++)dp[i][j] = inf;while (m–){rd(u); rd(v); rd(d);add(v, u, d);}bfs();int ans = inf;for (int i = 0; i <= c; i++)ans = min(ans, dp[1][i]);pt(ans); puts("");}return 0;}/*3 3 31 2 101 2 52 3 34 5 31 2 101 2 52 3 33 4 14 2 64 5 11 2 101 2 52 3 33 4 14 2 64 5 81 2 101 2 52 3 33 4 14 2 64 5 01 2 101 2 52 3 33 4 14 2 6*/
我不敢说我明天便可以做一个快乐的人，面朝大海春暖花开。
