[ABC164E] Two Currencies 题解

· · 题解

本题解未建图、未跑最短路，使用乱搞大法，码量大概是目前题解区最少的吧。

题意简述

有 n 个城市，它们由 m 条双向道路连接，保证它们能够彼此到达。第 i 条道路连接 u_i,v_i，需要花费 x_i 个银币，耗费 t_i 秒的时间。每个城市处都有兑换银币处，第 i 个城市中你可以用 1 个金币兑换 c_i 个银币，可以兑换无限次，不过兑换 1 次需要花费 d_i 秒的时间。你一开始在 1 号城市，有 s 个银币和无限多的金币，求到其它城市需要耗费的最小时间。

解题思路

考虑 dp。设 dp_{i,j} 表示在 i 城市，有 j 个银币时所需的最短时间。显然，转移方式有两种，一种是从一个城市走到另一个城市，一种是兑换银币。这两种转移的式子对应如下：

dp_{u,j-x}=\min(dp_{u,j-x},dp_{v,j}+t) dp_{i,j}=\min(dp_{i,j},dp_{i,j-c}+d)

其中 u,v,x,t,c,d 均为题中所给条件，下标已省略，i,j 为枚举的变量。

然后考虑把上面两个东西转移个 100 次，就可以通过本题了。正确性方面，我个人感觉是类似 bellman-ford，借助本题数据范围小的特点，所以转移 100 次就对了。

代码示例

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s,u[10010],v[10010],x[10010],t[10010];
int c[10010],d[10010],dp[55][2510];
signed main(){
    memset(dp,0x3f,sizeof(dp));
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++) cin>>u[i]>>v[i]>>x[i]>>t[i];
    for(int i=1;i<=n;i++) cin>>c[i]>>d[i];
    s=min(s,2500ll);//银币太多是无用的
    dp[1][s]=0;//初始化
    for(int _=0;_<=100;_++){//转移100次
        for(int i=1;i<=n;i++){
            for(int j=c[i];j<=2500;j++) dp[i][j]=min(dp[i][j],dp[i][j-c[i]]+d[i]);
        }//兑换银币的转移
        for(int i=1;i<=m;i++){
            for(int j=x[i];j<=2500;j++){
                dp[u[i]][j-x[i]]=min(dp[u[i]][j-x[i]],dp[v[i]][j]+t[i]);
                dp[v[i]][j-x[i]]=min(dp[v[i]][j-x[i]],dp[u[i]][j]+t[i]);
            }
        }//城市的转移，这个和bellman-ford几乎一样
    }
    for(int i=2;i<=n;i++){
        int ans=0x3f3f3f3f3f3f3f3f;
        for(int j=0;j<=2500;j++) ans=min(ans,dp[i][j]);
        cout<<ans<<endl;
    }
    return 0;
}