PAT1018. Public Bike Management

xiaoxiao2021-03-25 115

#include <iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<vector> using namespace std; const int maxn=550; const int inf=1000000000; int c,n,x,m; int b[maxn]; int G[maxn][maxn]; int vis[maxn]={0}; vector<int>pre[maxn]; vector<int>temppath,path;//设置保存当前路径的向量和最优路径的向量 int d[maxn]; int minneed=inf,minremain=inf; void dij(int s) { d[s]=0; for(int i=0; i<n; i++)//这里只要n次就够了 { int min=inf; int u=-1; for(int j=0; j<=n; j++)//因为算上起点总共有n+1个 { if(min>d[j]&&!vis[j]) { u=j; min=d[j]; } } if(u==-1)return; else { vis[u]=1; for(int j=0; j<=n; j++) if(G[u][j]!=inf&&vis[j]==0) { if(d[u]+G[u][j]<d[j]) { d[j]=d[u]+G[u][j]; pre[j].clear(); pre[j].push_back(u); } else if(d[u]+G[u][j]==d[j]) pre[j].push_back(u); } } } } void dfs(int e) { if(e==0) { temppath.push_back(e); int remain=0; int need=0; for(int i=temppath.size()-1; i>=0; i--) { int v=temppath[i]; if(b[v]>0) { remain+=b[v]; } else { if(remain>abs(b[v])) { remain+=b[v]; } else { need+=abs(b[v])-remain;//从起点带出来的车辆数是不断累加的 remain=0; } } } if(need<minneed) { minneed=need; path=temppath; minremain=remain; } else if(need==minneed&&remain<minremain) { path=temppath; minremain=remain; } temppath.pop_back(); return; } temppath.push_back(e); for(int i=0; i<pre[e].size(); i++) { int v=pre[e][i]; dfs(v); } temppath.pop_back(); } int main() { freopen("d://jin.txt","r",stdin); cin>>c>>n>>x>>m; fill(d,d+maxn,inf); fill(G[0],G[0]+maxn*maxn,inf);//必须这样初始化，如果在声明时={inf}只有第一个数是inf,其他都是0 for(int i=1; i<=n; i++) { int e; cin>>e; b[i]=e-c/2; } for(int i=0; i<m; i++) { int u,v,w; cin>>u>>v>>w; G[u][v]=G[v][u]=w; } dij(0); dfs(x); cout<<minneed<<' '; for(int i=path.size()-1; i>=0; i--) {cout<<path[i]; if(i>0)cout<<"->"; } cout<<' '<<minremain; return 0; }

转载请注明原文地址: https://ju.6miu.com/read-12324.html

技术

最新回复(0)