2025-四川省赛-A. Minimum Product（类似于floyd的图上dp）

思路讲解

类似于Floyd的递推公式

Untitled

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]。

2. 当外层循环执行到 c = 2 时，它会用所有 dp[...][0] 和 dp[...][1] 的值来更新 dp[...][2]。

3. …

4. 当我们计算 dp[...][c] 这一“层”的所有状态时，所有 c 值更小的“层”（比如 dp[...][c-1], dp[...][c-2] 等）都已经计算完毕并且得到了最优解。

这确保了我们每次进行状态转移时，dp[u[i]][c - a[i]] 已经是我们能找到的、到达节点 u 且 a 和为 c - a[i] 的最优值（即最小 b 和）。

AC代码

327896817

源代码

// 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……）