1018. Public Bike Management (30)

考察最短路，以及記錄相同長度最短路，然後遍歷選擇最優最短路 [cpp]  #include<iostream>   #include<vector>   #include<queue>   #include<stack>   using namespace std;      #define INF 0x6FFFFFFF   int Cmax, n, Sp, m;   typedef struct Edge   {       int v, dis;       Edge(int _v, int _dis):v(_v),dis(_dis){}   }Edge;      typedef struct Node   {       int c, dis;   }Node;   vector<vector<Edge>> edge;   vector<Node> city;   vector<vector<int>> allPath;   vector<bool> visited;      vector<int> bestPath;   int minSend = INF;   int minCollect = INF;   vector<int> possiblePath;   void FindBestPath(int u)   {       possiblePath.push_back(u);       if(u == 0)       {//find the end           int send = 0;           int collect = 0;           for(int i = possiblePath.size()-1; i >= 0; --i)           {               int t = possiblePath[i];               if(city[t].c > Cmax/2)                   collect += city[t].c - Cmax/2;               else if(city[t].c < Cmax/2)               {                   collect -= (Cmax/2-city[t].c);                   if(collect < 0) send -=collect, collect=0;               }           }           if(send < minSend) minSend=send, minCollect=collect, bestPath=possiblePath;           else if(send == minSend && collect < minCollect) minCollect=collect, bestPath=possiblePath;           return;       }       for(int i = 0; i < allPath[u].size(); ++i)       {           FindBestPath(allPath[u][i]);           possiblePath.pop_back();       }   }   int FindMin()   {       int mmin = INF;       int index = -1;       for(int i = 0; i <= n; ++i)       {           if(city[i].dis < mmin && !visited[i])           {               mmin = city[i].dis;               index = i;           }       }       return index;   }   void Dijkstra(int s, int t)   {       allPath.clear();       allPath.resize(n+1);       /*for(int i = 0; i <= n; ++i)          allPath[i].push_back(-1);*/       visited.assign(n+1, false);       for(int i = 0; i <= n; ++i)           city[i].dis = INF;       city[0].dis = 0;       while(true)       {           int u = FindMin();           if(u==-1) return;           visited[u] = true;           for(int i = 0; i < edge[u].size(); ++i)           {               int v = edge[u][i].v;               if(!visited[v])               {                   int dis = edge[u][i].dis;                   if(city[v].dis > city[u].dis+dis)                   {                       allPath[v].clear();                       city[v].dis = city[u].dis+dis;                       allPath[v].push_back(u);                   }                   else if(city[v].dis == city[u].dis+dis)                   {                       allPath[v].push_back(u);                   }               }           }       }      }   int main()   {       scanf("%d%d%d%d",&Cmax,&n,&Sp,&m);       city.clear();       city.resize(n+1);       for(int i = 1; i <= n; ++i)       {           scanf("%d",&city[i].c);           city[0].c = Cmax/2;       }       edge.clear();       edge.resize(n+1);       for(int i = 0; i < m; ++i)       {           int a, b, c;           scanf("%d%d%d",&a,&b,&c);           edge[a].push_back(Edge(b,c));           edge[b].push_back(Edge(a,c));       }              //end of input       //1. using dijkstra find all the possible solution       Dijkstra(0, Sp); www.2cto.com     //2. enumerate all possible path and record the best one       FindBestPath(Sp);       //output the best solution       printf("%d 0",minSend);       for(int i = bestPath.size()-2; i >= 0; --i)           printf("->%d",bestPath[i]);       printf(" %d\n", minCollect);       return 0;   }