本文共 1869 字，大约阅读时间需要 6 分钟。

E - Two Currencies

题意：给你n节点m条边的无向图

每条边有s 和 t ，s 代表 经过这条路要花费s银币，t代表走这条路需要消耗的时间

每个节点有c[i]、d[i] 代表在i这个节点兑换c个银币消耗d时间。

问从1节点出发  到达其他节点时的最小时间 

初始金币为s

做法：设dp[i][j] 代表 到达i这个节点拥有j银币时的最小时间。

进行n+1轮的图上dp即可。

注意要先枚举被到达的节点i  再枚举从起始点v->i 的dp转移。

如果是枚举i  ->v 会wa在倒数第二个点。原因不详。。

要从v的父亲转移过来，不能从v往外辐射，不知道是不是我代码问题 会wa在倒数第二个点

#include
   
    #define rep(i,a,b) for(int i=a;i<=(b);++i)#define per(i,a,b) for(int i=a;i>=(b);--i)#define mem(a,x) memset(a,x,sizeof(a))#define pb push_back#define pi pair
    
     #define mk make_pairusing namespace std;typedef long long ll;ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}const ll inf=0x3f3f3f3f;const int N=100;struct edge{    int v;    ll s,t;    int ne;}e[N<<1];int n,m,cnt,head[N];ll s,dis[N],c[N],d[N],dp[N][3000];void add(int u,int v,ll w,ll t){    e[++cnt]={v,w,t,head[u]};    head[u]=cnt;    e[++cnt]={u,w,t,head[v]};    head[v]=cnt;}void bfs(){    if(s>=2500) s=2500;    dp[1][s]=0;    for(int up=1;up<=n+2;++up){        for(int i=1;i<=n;++i){            for(int j=head[i];j;j=e[j].ne){                for(int now=0;now<=2500;++now){                    if(now+e[j].s>=0){                        dp[i][now]=min(dp[i][now],dp[e[j].v][now+e[j].s]+e[j].t);                //dp[e[j].v][now-e[j].s]=min(dp[e[j].v][now-e[j].s],dp[i][now]+e[j].t);                //这样wa                                   }                }            }            for(int now=0;now<=2500;now++){                if(now-c[i]>=0){                    dp[i][now]=min(dp[i][now-c[i]]+d[i],dp[i][now]);                }            }        }    }}void solve(){   cin>>n>>m>>s;   mem(dp,inf);   rep(i,1,m)   {       int u,v;ll a,b;       cin>>u>>v>>a>>b;       add(u,v,a,b);   }   rep(i,1,n) cin>>c[i]>>d[i];   bfs();   for(int i=2;i<=n;++i){        ll ans=1e18;        for(int now=0;now<=2500;++now) ans=min(ans,dp[i][now]);        printf("%lld\n",ans);   }}int main(){	solve();}
    
   

转载地址：https://ccsudeer.blog.csdn.net/article/details/105794508 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！