2025-四川省赛-A. Minimum Product（类似于floyd的图上dp） · znzryb
## 思路讲解
类似于Floyd的递推公式
Untitled
```cpp
FOR(j,0,sum){
FOR(i,0,SZ(edges)-1){
ll u,v,a,b;u=edges[i][0],v=edges[i][1],a=edges[i][2],b=edges[i][3];
if(dp[u][j]>=INF) continue;
dp[v][j+a]=min(dp[v][j+a],dp[u][j]+b);
}
}
```
**根本原因：保证状态转移的顺序正确性，避免“后效性”。**
动态规划的一个基本原则是，当你计算一个状态 `dp[S]` 时，所有它所依赖的状态 `dp[S']` 都必须是已经计算出来的、并且是最终的（最优的）值。
让我们来分析一下这个特定的状态转移 `dp[v[i]][c] = ... dp[u[i]][c - a[i]] ...`：
- 为了计算 `c` 这个总和的状态，我们依赖于 `c - a[i]` 这个总和的状态。
- 因为边权 `a[i]` 是正整数 (`a[i] >= 1`)，所以 `c - a[i]` 永远小于 `c`。
**将** **`c`** **(a的和) 作为外层循环，并从小到大枚举，就完美地解决了这个问题。**
1. 当外层循环执行到 `c = 1` 时，它会用所有 `dp[...][0]` 的值来更新 `dp[...][1]`。
1. 当外层循环执行到 `c = 2` 时，它会用所有 `dp[...][0]` 和 `dp[...][1]` 的值来更新 `dp[...][2]`。
1. ......
1. 当我们计算 `dp[...][c]` 这一“层”的所有状态时，所有 `c` 值更小的“层”（比如 `dp[...][c-1]`, `dp[...][c-2]` 等）都已经计算完毕并且得到了最优解。
这确保了我们每次进行状态转移时，`dp[u[i]][c - a[i]]` 已经是我们能找到的、到达节点 `u` 且 `a` 和为 `c - a[i]` 的最优值（即最小 `b` 和）。
## AC代码
327896817
::: 源代码
```cpp
// Problem: A. Minimum Product
// Contest: Codeforces - The 2025 Sichuan Provincial Collegiate Programming Contest
// URL: https://codeforces.com/group/vXvHT09g9Y/contest/105949/problem/A
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
using namespace std;
using ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll MAXM=(ll)1e3+10;
constexpr ll MAXV=(ll)300*200;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,lT;
// int A[310];
// int U[310],V[310],B[310];
/*
*/
// dp[i][j] A值为j的时候，最小的B值是多少（从1到达i点）
ll dp[310][MAXV];
vector<array<ll,4> > edges;
ll sum=0;
inline void init(){
sum=0;
FOR(i,0,SZ(edges)-1){
sum+=edges[i][2];
}
sum+=5;
FOR(i,0,N+5){
FOR(j,0,sum){
dp[i][j]=INF;
}
}
dp[1][0]=0;
}
inline void solve(){
cin>>N>>M;
edges.clear();
FOR(i,1,M){
int u,v,a,b;
cin>>u>>v>>a>>b;
edges.pb({u,v,a,b});
}
init();
sort(all(edges));
FOR(j,0,sum){
FOR(i,0,SZ(edges)-1){
ll u,v,a,b;u=edges[i][0],v=edges[i][1],a=edges[i][2],b=edges[i][3];
if(dp[u][j]>=INF) continue;
dp[v][j+a]=min(dp[v][j+a],dp[u][j]+b);
}
}
#ifdef LOCAL
FOR(i,1,N){
FOR(j,0,sum){
cerr<<dp[i][j]<<" ";
}
cerr<<"\n";
}
#endif
ll ans=INF,a=INF,b=INF;
FOR(i,0,sum){
if(dp[N][i]>=INF) continue;
if(dp[N][i]*i<ans){
ans=dp[N][i]*i;
a=i,b=dp[N][i];
}
}
cout<<a<<" "<<b<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>lT;
while(lT--)
solve();
return 0;
}
/*
AC
327896817
*/
```
:::
## 心路历程（WA，TLE，MLE……）