pat-1018 Public Bike Management 有问题
最后一个case还过不了 ==
为什么呢

思路dfs遍历到目标的所有路径
找最短，运送最少，带回最少的路径

#include <iostream>#include <vector>#include<memory.h>using namespace std;#define MAXV 501#define INFINITE 1000000000int mindis = INFINITE; int mincarry = INFINITE;int minback;vector<int> minpath;int status[MAXV];int use[MAXV];int map[MAXV][MAXV];vector<int> path;int curdis = 0;int capacity;int station;int target;int road;void dfs(int node,int target){if(node == target){for(int i = 0; i < path.size()-1 ; i++)curdis += map[path[i]][path[i+1]];int tmpstatus[MAXV];memset(tmpstatus,0,sizeof(tmpstatus));for(int i = 0;i<path.size();i++)tmpstatus[path[i]] = status[path[i]] - capacity/2;int carry = 0;int collect = 0; //collect from pathint tmp;if(curdis <= mindis){for(int i = 1 ;i <= station ;i++){tmp = collect + tmpstatus[i];if(tmp < 0){carry -= tmp;collect = 0;}else if(tmp >= 0){collect = tmp;}}}if(curdis < mindis){mindis = curdis;mincarry = carry;minback = collect;minpath = path;}else if(curdis == mindis){if(carry < mincarry ){mincarry = carry;minback = collect;minpath = path;}else if(carry == mincarry && collect < minback){minback = collect;minpath = path;}}curdis = 0;}else{//all the node that current node can reachfor(int v=0;v<MAXV;v++)if(map[node][v])        {            if(use[v]==false) //avoid loop            {path.push_back(v);use[v] = 1;dfs(v,target);use[v] = 0;path.pop_back();}}}}int main(){int x,y;int time;cin>>capacity>>station>>target>>road;memset(status,0,sizeof(status));for(int i = 1 ; i <= station ; i++)cin>>status[i];memset(map,0,sizeof(map));for(int i = 0; i < road ; i++){cin>>x>>y>>time;map[x][y] = time;map[y][x] = time;}path.push_back(0);use[0] = 1;dfs(0,target);use[0] = 0;path.pop_back();cout<<mincarry<<" ";for(int i = 0 ;i<minpath.size();i++){cout<<minpath[i];if(i != minpath.size() -1 )cout<<"->";}cout<<" "<<minback<<endl;}