uva10603fill

这道题说是能让更加理解  搜索和djk  spfa最短路这些东西之间的关系。。。 先做题，，没办法那么理清楚关系 #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<string> #include<cstring> #include<iomanip> #include<iostream> #include<stack> #include<cmath> #include<map> #include<vector> #define ll long long #define inf 0x3f3f3f3f #define INF 1000000000 #define bug1 cout<<"bug1"<<endl; #define bug2 cout<<"bug2"<<endl; #define bug3 cout<<"bug3"<<endl; using namespace std; const int maxn=205; struct Node{ int v[3],dist; bool operator <(const Node&rhs)const{ return dist>rhs.dist; } }; int vis[maxn][maxn]; int cap[3]; int ans[100000]; bool update_ans(Node u){ int flag=0; for(int i=0;i<3;++i){ int d=u.v[i]; if(ans[d]<0||ans[d]>u.dist){ flag=1; ans[d]=u.dist; } } if(flag)return true; return false; } void solve(int a,int b,int c,int d){ cap[0]=a;cap[1]=b;cap[2]=c; memset(vis,0,sizeof(vis)); memset(ans,-1,sizeof(ans)); priority_queue<Node>que; Node s; s.v[0]=0;s.v[1]=0;s.v[2]=c;s.dist=0; vis[0][0]=1; que.push(s); update_ans(s); while(!que.empty()){ Node u=que.top();que.pop(); if(ans[d]>=0)break; for(int i=0;i<3;++i){ for(int j=0;j<3;++j){ if(i==j)continue; if(u.v[i]==0||u.v[j]==cap[j])continue; int amount=min(cap[j],u.v[i]+u.v[j])-u.v[j]; Node u2=u; u2.dist=u.dist+amount; u2.v[i]-=amount; u2.v[j]+=amount; if(update_ans(u2)){//执行了 更新操作，就看能不能放入， if(!vis[u2.v[0]][u2.v[1]]){//如果发现已经用过的，就不放 vis[u2.v[0]][u2.v[1]]=1; que.push(u2); } } } } } while(d>=0){ if(ans[d]>=0){ printf("%d %d\n",ans[d],d); return; } d--; } } int main(){ int t; scanf("%d",&t); while(t--){ int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); solve(a,b,c,d); } }