学步园

这道题还是蛮好理解的！就是先跑一边最短路，然后用01背包模型进行求解！因为题是说有足够多的车子从0点出发，也就是看我们要控制到大于一半的油所需的最短路径！就是利用01背包看是否取这条路径！

下面用dijkstra实现单源最短路径

#include<iostream><br /> #include<cstdlib><br /> #include<stdio.h><br /> #include<cstring><br /> using namespace std;<br /> const int inf=900000000,Max=120;<br /> int dp[450000000];<br /> int d[10400],m[Max][Max],known[Max],cost[Max];<br /> void dijkstra(int n)<br /> {<br /> int i,j,temp,index;<br /> for(i=0;i<=n;i++)<br /> {<br /> d[i]=inf;<br /> known[i]=0;<br /> }<br /> for(i=0;i<=n;i++)<br /> {<br /> if(m[0][i]<inf)<br /> d[i]=m[0][i];<br /> }<br /> known[0]=1;<br /> d[0]=0;<br /> for(i=0;i<n;i++)<br /> {<br /> temp=inf;<br /> index=-1;<br /> for(j=0;j<=n;j++)<br /> {<br /> if(temp>d[j]&&known[j]==0)<br /> {<br /> temp=d[j];<br /> index=j;<br /> }<br /> }<br /> if(index==-1)<br /> break;<br /> known[index]=1;<br /> for(j=0;j<=n;j++)<br /> {<br /> if(m[index][j]<inf&&known[j]==0)<br /> {<br /> if(d[j]>m[index][j]+d[index])<br /> d[j]=m[index][j]+d[index];<br /> }<br /> }<br /> }<br /> }<br /> int main()<br /> {<br /> int N,M,i,j,s,e,T,sum;<br /> scanf("%d",&T);<br /> while(T--)<br /> {<br /> scanf("%d%d",&N,&M);<br /> sum=0;<br /> for(i=0;i<=N;i++)<br /> for(j=0;j<=N;j++)<br /> {<br /> if(i==j)<br /> m[i][j]=0;<br /> else<br /> m[i][j]=inf;<br /> }<br /> for(i=0;i<M;i++)<br /> {<br /> scanf("%d%d%d",&s,&e,&j);<br /> m[s][e]=m[e][s]=(min(j,m[s][e]));<br /> }<br /> cost[0]=0;<br /> for(i=1;i<=N;i++)<br /> {<br /> scanf("%d",&cost[i]);<br /> sum+=cost[i];<br /> }<br /> dijkstra(N);<br /> dp[0]=0;<br /> for(i=1;i<=sum+1;i++)<br /> dp[i]=inf;<br /> for(i=0;i<=N;i++)<br /> {<br /> for(j=sum;j>=cost[i];j--)<br /> {<br /> if(dp[j-cost[i]]<inf)<br /> dp[j]=min(dp[j],dp[j-cost[i]]+d[i]);<br /> }<br /> }//之前是直接输出dp[sum/2+1]结果一直在wa，后来看了别人的代码，发现者不一定是对的！就想起了以前看过的关于背包<br /> //专题的介绍！因为dp[i]<=dp[i+1],所以sum/2+1的路径的最小值应该是dp[sum/2+1]到dp[sum+1]的一个最小值<br /> j=dp[sum+1];<br /> for(i=sum;i>=sum/2+1;i--)<br /> if(j>dp[i])<br /> j=dp[i];<br /> if(j<inf)<br /> printf("%d/n",j);<br /> else<br /> printf("impossible/n");<br /> }<br /> return 0;<br /> }</p> <p>

下面使用spfa实现，不过是用手写的队列，反而时间耗的更多了！还是用STL方便啊！

#include<iostream><br /> #include<cstdlib><br /> #include<cstring><br /> #include<stdio.h><br /> using namespace std;<br /> const int inf=900000000,Max=120,Maxsum=450000000;<br /> int m[Max][Max],d[Max],dp[Maxsum],in[Max],cost[Max],q[Max];<br /> void spfa(int n)<br /> {<br /> int i,temp,front,rear;<br /> for(i=0;i<=n;i++)<br /> d[i]=inf;<br /> d[0]=0;<br /> memset(in,0,sizeof(in));<br /> front=rear=-1;<br /> q[++rear]=0;<br /> in[0]=1;<br /> while(front<rear)<br /> {<br /> temp=q[++front];<br /> in[temp]=0;<br /> for(i=0;i<=n;i++)<br /> {<br /> if(m[temp][i]<inf)<br /> {<br /> if(d[i]>d[temp]+m[temp][i])<br /> {<br /> d[i]=d[temp]+m[temp][i];<br /> if(in[i]==0)<br /> {<br /> q[++rear]=i;<br /> in[i]=1;<br /> }<br /> }<br /> }<br /> }<br /> }<br /> }<br /> int main()<br /> {<br /> int N,M,i,j,sum,T,s,e;<br /> scanf("%d",&T);<br /> while(T--)<br /> {<br /> scanf("%d%d",&N,&M);<br /> for(i=0;i<=N;i++)<br /> for(j=0;j<=N;j++)<br /> {<br /> if(i==j)<br /> m[i][j]=0;<br /> else<br /> m[i][j]=inf;<br /> }<br /> for(i=0;i<M;i++)<br /> {<br /> scanf("%d%d%d",&s,&e,&j);<br /> m[s][e]=m[e][s]=min(j,m[s][e]);<br /> }<br /> sum=0;<br /> for(i=1;i<=N;i++)<br /> {<br /> scanf("%d",&cost[i]);<br /> sum+=cost[i];<br /> }<br /> cost[0]=0;<br /> spfa(N);<br /> // for(i=0;i<=N;i++)<br /> // cout<<d[i]<<" ";<br /> // cout<<endl;<br /> // cout<<endl;<br /> for(i=0;i<=sum+1;i++)<br /> dp[i]=inf;<br /> dp[0]=0;<br /> for(i=0;i<=N;i++)<br /> for(j=sum;j>=cost[i];j--)<br /> {<br /> if(dp[j-cost[i]]<inf)<br /> if(dp[j]>dp[j-cost[i]]+d[i])<br /> dp[j]=dp[j-cost[i]]+d[i];<br /> dp[j]=min(dp[j],dp[j+1]);//如果不加这一句，就应该是dp[sum/2+1]到dp[sum]的最小值了<br /> }<br /> // for(i=0;i<=sum;i++)<br /> // cout<<dp[i]<<" ";<br /> /* j=inf;<br /> for(i=sum;i>=sum/2+1;i--)<br /> if(j>dp[i])<br /> j=dp[i];*/<br /> if(dp[sum/2+1]<inf)<br /> printf("%d/n",dp[sum/2+1]);<br /> else<br /> printf("impossible/n");<br /> }<br /> return 0;<br /> }<br />