1018. Public Bike Management (30)

题目链接：https://www.patest.cn/contests/pat-a-practise/1018

---

题目大意：先求最短路径，若有多条最短路径，优先选择需要从源点运出自行车最少的那条，若还相同的话，选择需要收回到源点的自行车最少的那条，题目保证结果唯一。

---

解题思路：

Dijkstra算法求最短路径，并保存下来DFS遍历所有的最短路径，求出这些路径中send、back最小的那个。

---

#include <iostream> #include <vector> using namespace std; int edge[501][501],dist[501],visit[501]={0},w[501]; vector<int> pre[501]; const int MAX=99999999; vector<int> path,tmp; int minsend=MAX,minback=MAX; int Cmax,N,Sp,M; /*从终点反向深度优先地遍历所有最短路径 对与每个最短路径，计算相应的send和back。 然后判断是不是最小的send，最小的back*/ void dfs(int v){ if(v==0){//遍历到0时停止，开始处理该路径 int send=0,back=0; /*开始计算当前路径的send和back*/ for(int i=tmp.size()-1;i>=0;i--){ if(w[tmp[i]]<=Cmax/2){//不足一半 if((Cmax/2-w[tmp[i]])>=back){//并且当前要back的小于需求的 send+=(Cmax/2-w[tmp[i]]-back);//跟新send back=0;//back置0 } else//当前要back的足以满足需求 back-=(Cmax/2-w[tmp[i]]); } else//超过一半更新back back+=(w[tmp[i]]-Cmax/2); } /*将当前的send和back与当前的minsend和minback比较*/ if(send<minsend){ minsend=send; minback=back; path=tmp; } else if(send==minsend&&back<minback){ minback=back; path=tmp; } return; } tmp.push_back(v);//不等于0的话就先记录在临时路径中 for(int i=0;i<pre[v].size();i++){//递归遍历该点的所有前置结点 dfs(pre[v][i]); } tmp.pop_back();//该结点的前置结点都遍历完之后将该结点从路径删除 } int main(int argc, char const *argv[]) { cin>>Cmax>>N>>Sp>>M; for(int i=0;i<=500;i++) for(int j=0;j<=500;j++) edge[i][j]=MAX; for(int i=1;i<=N;i++){ cin>>w[i]; dist[i]=MAX; } int a,b,d;//边的两个端点 for(int i=0;i<M;i++){ cin>>a>>b>>d; edge[a][b]=edge[b][a]=d; } /*开始Dijkstra求最短路径*/ dist[0]=0; for(int i=0;i<=N;i++){ int current=-1,min=MAX; for(int j=0;j<=N;j++){ if(visit[j]==0&&dist[j]<min){ current=j; min=dist[j]; } } if(current==-1) break; visit[current]=1; for(int j=0;j<=N;j++){ if(visit[j]==0&&edge[current][j]!=MAX){ if(edge[current][j]+dist[current]<dist[j]){ dist[j]=edge[current][j]+dist[current]; pre[j].clear(); pre[j].push_back(current); } else if(edge[current][j]+dist[current]==dist[j]) pre[j].push_back(current); } } } dfs(Sp); cout<<minsend<<" 0"; for(int i=path.size()-1;i>=0;i--) cout<<"->"<<path[i]; cout<<" "<<minback<<endl; return 0; }