題干：

鏈接：https://www.nowcoder.com/questionTerminal/4b20ed271e864f06ab77a984e71c090f
來源：牛客網(wǎng)
There is a public bike service in Hangzhou City which provides great convenience to the tourists from all over the world. One may rent a bike at any station and return it to any other stations in the city.
The Public Bike Management Center (PBMC) keeps monitoring the real-time capacity of all the stations. A station is said to be in perfect condition if it is exactly half-full. If a station is full or empty, PBMC will collect or send bikes to adjust the condition of that station to perfect. And more, all the stations on the way will be adjusted as well.
When a problem station is reported, PBMC will always choose the shortest path to reach that station. If there are more than one shortest path, the one that requires the least number of bikes sent from PBMC will be chosen.

Figure 1
Figure 1 illustrates an example. The stations are represented by vertices and the roads correspond to the edges. The number on an edge is the time taken to reach one end station from another. The number written inside a vertex S is the current number of bikes stored at S. Given that the maximum capacity of each station is 10. To solve the problem at S3 , we have 2 different shortest paths:
1. PBMC -> S1 -> S3 . In this case, 4 bikes must be sent from PBMC, because we can collect 1 bike from S1 and then take 5 bikes to S3 , so that both stations will be in perfect conditions.
2. PBMC -> S2 -> S3 . This path requires the same time as path 1, but only 3 bikes sent from PBMC and hence is the one that will be chosen.

輸入描述:

Each input file contains one test case. For each case, the first line contains 4 numbers: Cmax (<= 100), always an even number, is the maximum capacity of each station; N (<= 500), the total number of stations; Sp, the index of the problem station (the stations are numbered from 1 to N, and PBMC is represented by the vertex 0); and M, the number of roads. The second line contains N non-negative numbers Ci (i=1,...N) where each Ci is the current number of bikes at Si respectively. Then M lines follow, each contains 3 numbers: Si, Sj, and Tij which describe the time Tij taken to move betwen stations Si and Sj. All the numbers in a line are separated by a space.

?

輸出描述:

For each test case, print your results in one line. First output the number of bikes that PBMC must send. Then after one space, output the path in the format: 0->S1->...->Sp. Finally after another space, output the number of bikes that we must take back to PBMC after the condition of Sp is adjusted to perfect. Note that if such a path is not unique, output the one that requires minimum number of bikes that we must take back to PBMC. The judge's data guarantee that such a path is unique.

示例1

輸入

10 3 3 5 6 7 0 0 1 1 0 2 1 0 3 3 1 3 1 2 3 1

輸出

3 0->2->3 0

再給一組樣例：
100 6 1 15
78 54 0 37 36 82
0 1 7
0 2 4
0 3 7
0 4 7
0 5 2
1 2 9
1 3 1
1 4 2
1 5 5
2 3 1
2 4 2
2 5 7
3 4 4
3 5 7
4 5 7
對應(yīng)輸出應(yīng)該為:
46 0->2->3->1 28

題目大意：每個自行車車站的最大容量為一個偶數(shù)cmax，如果一個車站里面自行車的數(shù)量恰好為cmax / 2，那么稱處于完美狀態(tài)。如果一個車站容量是滿的或者空的，控制中心（處于結(jié)點0處）就會攜帶或者從路上收集一定數(shù)量的自行車前往該車站，一路上會讓所有的車站沿途都達到完美。現(xiàn)在給出cmax，車站的數(shù)量n，問題車站sp，m條邊，還有距離，求最短路徑。如果最短路徑有多個，求能帶的最少的自行車數(shù)目的那條。如果還是有很多條不同的路，那么就找一個從車站帶回的自行車數(shù)目最少的。帶回的時候是不調(diào)整的

解題報告：

? ?這題解法多種多樣，此處列舉二三。

AC代碼1：（雙dfs）

#include<bits/stdc++.h>using namespace std; const int INF = 0x3f3f3f3f; int maze[505][505]; int val[505],dis[505]; bool vis[505]; int ans; int c,n,s,m; void Dijkstra() {memset(dis,INF,sizeof dis);memset(vis,0,sizeof vis);dis[0]=0;int all = n+1,minw,minv;while(all--) {minw = INF;for(int i = 0; i<=n; i++) {if(vis[i]) continue;if(dis[i] < minw) {minw = dis[i];minv = i;}}vis[minv] = 1;for(int i = 0; i<=n; i++) {if(vis[i] || maze[minv][i] == INF) continue;dis[i] = min(dis[i],dis[minv] + maze[minv][i]);}} } void dfs(int x,int res) {if(res < 0) return ;if(x == s) {ans = min(ans,res);return ;}for(int i = 0; i<=n; i++) {if(maze[x][i] == INF) continue;if(dis[i] == dis[x] + maze[x][i]) dfs(i,res - (c-val[i]));} } bool Dfs(int x, int y, int z) {if (x==0) {if (y == z) {printf("0");return 1;} else return 0;}for (int i = 0; i <= n; i++) {if (maze[x][i] == -1) continue;if (dis[x] == dis[i] + maze[x][i]) {if (Dfs(i, y + c - val[x], z)) {printf("->%d", x);return 1;}}}return 0; }int main() {int a,b,w;cin>>c>>n>>s>>m;c>>=1;for(int i = 1; i<=n; i++) scanf("%d",val+i);memset(maze,INF, sizeof maze);for(int i = 1; i<=m; i++) {scanf("%d%d%d",&a,&b,&w);if(w < maze[a][b]) maze[a][b] = maze[b][a] = w;}Dijkstra();int l = 0,r = n*c;int mid = (l+r)/2;while(l < r) {mid = (l+r)/2;ans = INF;dfs(0,mid);if(ans == INF) l = mid+1;else r=mid;}printf("%d ",l);dfs(0,l);Dfs(s,ans,l);printf(" %d\n", ans);return 0 ; }

此法先用鄰接矩陣存圖，然后跑Dijkstra求出1號點到各點的最短路，然后二分答案從中心帶出多少輛車，順便求出需要帶回多少輛車，因為數(shù)據(jù)保證有且唯一正確的路徑，所以倒序找到路徑，一定能找到、、、、總之不是很好理解。

?

AC代碼2：

#include<bits/stdc++.h> using namespace std; const int inf = 0x3f3f3f3f; int cmax, n, sp, m; int minNeed = inf, minBack = inf; int e[510][510], dis[510], weight[510]; bool vis[510]; vector<int> pre[510]; vector<int> path, temppath; void dfs(int v) {temppath.push_back(v);if(v == 0) {int need = 0, back = 0;for(int i = temppath.size() - 1; i >= 0; i--) {int id = temppath[i];if(weight[id] > 0) {back += weight[id];} else {if(back > (0 - weight[id])) {back += weight[id];} else {need += ((0 - weight[id]) - back);back = 0;}}}if(need < minNeed) {minNeed = need;minBack = back;path = temppath;} else if(need == minNeed && back < minBack) {minBack = back;path = temppath;}temppath.pop_back();return ;}for(int i = 0; i < pre[v].size(); i++)dfs(pre[v][i]);temppath.pop_back(); } int main() {memset(e,inf,sizeof e);memset(dis,inf,sizeof dis);scanf("%d%d%d%d", &cmax, &n, &sp, &m);for(int i = 1; i <= n; i++) {scanf("%d", &weight[i]);weight[i] = weight[i] - cmax / 2;}for(int i = 0; i < m; i++) {int a, b;scanf("%d%d", &a, &b);scanf("%d", &e[a][b]);e[b][a] = e[a][b];}dis[0] = 0;for(int i = 0; i <= n; i++) {int u = -1, minn = inf;for(int j = 0; j <= n; j++) {if(vis[j] == false && dis[j] < minn) {u = j;minn = dis[j];}}if(u == -1) break;vis[u] = true;for(int v = 0; v <= n; v++) {if(vis[v] == false && e[u][v] != inf) {if(dis[v] > dis[u] + e[u][v]) {dis[v] = dis[u] + e[u][v];pre[v].clear();pre[v].push_back(u);} else if(dis[v] == dis[u] + e[u][v]) {pre[v].push_back(u);}}}}dfs(sp);printf("%d 0", minNeed);for(int i = path.size() - 2; i >= 0; i--)printf("->%d", path[i]);printf(" %d", minBack);return 0; }

這種方法相對來說較好理解，就是先dijkstra跑出最短路條數(shù)并且記錄路徑，然后dfs搜索出最優(yōu)路徑

分析：Dijkstra + DFS。如果只有Dijkstra是不可以的，因為minNeed和minBack在路徑上的傳遞不滿足最優(yōu)子結(jié)構(gòu)，不是簡單的相加的過程，只有在所有路徑都確定了之后才能去選擇最小的need和最小的back。
Dijkstra求最短路徑，dfs求minNeed和minBack和path，dfs的時候模擬一遍需要調(diào)整的過程，求出最后得到的need和back，與minNeed和minBack比較然后根據(jù)情況更新path，最后輸出minNeed path 和 minBack，記得path是從最后一個結(jié)點一直到第一個結(jié)點的，所以要倒著輸出~

?

AC代碼3：

這個更不知道為什么了。。甚至回溯都沒看懂，為啥注釋那一行加上，for中那一行去掉，就不對了

#include <bits/stdc++.h> using namespace std; const int maxn=500+5,INF=1e9; int cap,n,sp,m,bike[maxn],cost[maxn][maxn]; vector<int> G[maxn],anspath,curpath; int minsend=INF,minback=INF,mincost=INF,vis[maxn]; void dfs(int cur,int cursend,int curback,int curcost){vis[cur]=1;curpath.push_back(cur);if(curcost>mincost) return ;if(cur==sp){if(curcost<mincost){mincost=curcost;minsend=cursend;minback=curback;anspath=curpath;return ;}if(curcost==mincost&&cursend<minsend){mincost=curcost;minsend=cursend;minback=curback;anspath=curpath;return ; }if(curcost==mincost&&cursend==minsend&&curback<minback){mincost=curcost;minsend=cursend;minback=curback;anspath=curpath;return ;}return ;}for(int i=0;i<G[cur].size();++i){int v=G[cur][i];if(!vis[v]){if(bike[v]+curback<cap/2) dfs(v,cursend+cap/2-bike[v]-curback,0,curcost+cost[cur][v]);else dfs(v,cursend,curback+bike[v]-cap/2,curcost+cost[cur][v]);vis[v]=0;curpath.pop_back(); }} // vis[cur]=0;curpath.pop_back(); } int main(){scanf("%d %d %d %d",&cap,&n,&sp,&m);for(int i=1;i<=n;++i) scanf("%d",&bike[i]);for(int i=1,x,y,z;i<=m;++i){scanf("%d %d %d",&x,&y,&z);G[x].push_back(y);G[y].push_back(x);cost[x][y]=z;cost[y][x]=z; }dfs(0,0,0,0);printf("%d ",minsend);for(int i=0;i<anspath.size();++i)if(i==0) printf("%d",anspath[i]);else printf("->%d",anspath[i]); printf(" %d\n",minback);return 0; }

（更新：知道為什么了，，因為前面有的地方就return了，就沒執(zhí)行popback這行了，樣例都過不了，所以保險起見，還是改成for循環(huán)中vis=1和vis=0吧，改成這樣:）

void dfs(int cur,int cursend,int curback,int curcost){ // vis[cur]=1;curpath.push_back(cur);if(curcost>mincost) return ;if(cur==sp){if(curcost<mincost){mincost=curcost;minsend=cursend;minback=curback;anspath=curpath;return ;}if(curcost==mincost&&cursend<minsend){mincost=curcost;minsend=cursend;minback=curback;anspath=curpath;return ; }if(curcost==mincost&&cursend==minsend&&curback<minback){mincost=curcost;minsend=cursend;minback=curback;anspath=curpath;return ;}return ;}for(int i=0;i<G[cur].size();++i){int v=G[cur][i];if(!vis[v]){vis[v] = 1;curpath.push_back(v);if(bike[v]+curback<cap/2) dfs(v,cursend+cap/2-bike[v]-curback,0,curcost+cost[cur][v]);else dfs(v,cursend,curback+bike[v]-cap/2,curcost+cost[cur][v]);vis[v]=0;curpath.pop_back(); }} // vis[cur]=0;curpath.pop_back(); }

并且在主函數(shù)的dfs前：?

vis[0]=1;curpath.push_back(0);

?

AC代碼4：

但是感覺還是復(fù)雜度有點高，并且不穩(wěn)定，我給他改了一下，變成簡單易懂的了。。

#include<bits/stdc++.h> using namespace std; const int maxn=500+5,INF=0x3f3f3f3f; int cap,n,sp,m,bike[maxn],cost[maxn][maxn]; vector<int> G[maxn],anspath,curpath; int minsend=INF,minback=INF,mincost=INF,vis[maxn]; int dis[maxn]; void Dijkstra() {int all = n+1;bool visit[maxn] = {0};memset(dis,INF,sizeof dis);dis[0]=0;while(all--) {int minv,minw = INF;for(int i = 0; i<=n; i++) {if(visit[i]==0 && dis[i] < minw) minw=dis[i],minv=i;}visit[minv]=1;for(int i = 0; i<G[minv].size(); i++) {int now = G[minv][i];if(visit[now] == 0 && dis[now] > dis[minv] + cost[minv][now]) dis[now] = dis[minv] + cost[minv][now];}} } void dfs(int cur,int cursend,int curback,int curcost){if(curcost>mincost) return ;if(cur==sp){if(cursend<minsend){minsend=cursend;minback=curback;anspath=curpath;return ; }if(cursend==minsend&&curback<minback){minsend=cursend;minback=curback;anspath=curpath;return ;}return ;}for(int i=0;i<G[cur].size();i++){int v=G[cur][i];if(!vis[v]){vis[v] = 1;curpath.push_back(v);if(bike[v]+curback<cap/2) dfs(v,cursend+cap/2-bike[v]-curback,0,curcost+cost[cur][v]);else dfs(v,cursend,curback+bike[v]-cap/2,curcost+cost[cur][v]);vis[v]=0;curpath.pop_back();}} } int main(){scanf("%d %d %d %d",&cap,&n,&sp,&m);for(int i=1;i<=n;++i) scanf("%d",&bike[i]);for(int i=1,x,y,z;i<=m;++i){scanf("%d %d %d",&x,&y,&z);G[x].push_back(y);G[y].push_back(x);cost[x][y]=z;cost[y][x]=z; }Dijkstra();mincost = dis[sp];vis[0]=1;curpath.push_back(0); dfs(0,0,0,0);printf("%d ",minsend);for(int i=0;i<anspath.size();++i)if(i==0) printf("%d",anspath[i]);else printf("->%d",anspath[i]); printf(" %d\n",minback);return 0; }

AC代碼5：

還算能看懂的：（其實和AC代碼3差不多、、）

#include<iostream> #include<fstream> #include<vector> using namespace std; #define MAX 505 #define INF 10000int cap,N,sp,M; int vex; int dist[MAX][MAX]; int bike[MAX]; #define PF cap/2vector<int> curpath; vector<int> shortpath; int minsend=INF,minback=INF; int minlen=INF; int cursend=0,curback=0; int curlen=0; bool visit[MAX]= {0};void dfs(int cur) {if(curlen>minlen)return;if(cur==sp) {//到達目標點，看是否最優(yōu)if(curlen<minlen) {minlen=curlen;minsend=cursend;minback=curback;shortpath=curpath;} else if(curlen==minlen) {if(cursend<minsend||(cursend==minsend&&curback<minback)) {minsend=cursend;minback=curback;shortpath=curpath;}}return;}for(int i=1; i<vex; i++) {if(visit[i]==true||dist[cur][i]==INF)continue;int lastsend=cursend;int lastback=curback;//計算到達當前點的send和back數(shù)if(bike[i]+curback<PF) {cursend+=PF-bike[i]-curback;curback=0;} else {curback=bike[i]+curback-PF;}visit[i]=true;curpath.push_back(i);curlen+=dist[cur][i];dfs(i);curpath.pop_back();visit[i]=false;curlen-=dist[cur][i];cursend=lastsend;curback=lastback;} } int main() {cin>>cap>>N>>sp>>M;//初始化,距離置為INFvex=N+1;for(int i=0; i<vex; i++) {for(int j=0; j<vex; j++) {dist[i][j]=dist[j][i]=INF;}}for(int i=1; i<vex; i++) cin>>bike[i];for(int k=0; k<M; k++) {int i,j;cin>>i>>j>>dist[i][j];dist[j][i]=dist[i][j];}dfs(0);printf("%d 0",minsend);for(int i=0; i<shortpath.size(); i++) {printf("->%d",shortpath[i]);}printf(" %d",minback);return 0; }

?

ps：wjh大佬寫了個Dijkstra不加dfs，有點小問題但是也AC了，但是這個代碼也告訴我們?yōu)槭裁催@題不能用Dijkstra而應(yīng)該加上dfs。

#include<bits/stdc++.h> using namespace std; struct node {int id;int d;int next; } side[12000]; int head[1200]; int dis[1200]; int book[1200]; int cm,n,m,sp,cmax; int num[1000]; int f[1000]; int dc[1000],tz[1000]; int cnt=0; void init() {for(int i=0; i<=800; i++) {f[i]=i;}memset(dc,0x3f3f3f3f,sizeof(dc));memset(tz,0,sizeof(tz));memset(num,0,sizeof(num));memset(head,-1,sizeof(head));memset(dis,0x3f3f3f3f,sizeof(dis));memset(book,0,sizeof(book));cnt=0; } void add(int x,int y,int d) {side[cnt].id=y;side[cnt].d=d;side[cnt].next=head[x];head[x]=cnt++; } struct nod {int id;int d;nod() {}nod(int id,int d):id(id),d(d) {}friend bool operator<(nod a,nod b) {return a.d>b.d;} }; void printpath(int x) {if(f[x]==x) {printf("0");return;} else {printpath(f[x]);printf("->%d",x);} } void dijkstra(int sx,int ex) {priority_queue<nod> q;q.push(nod(sx,0));dis[sx]=0;dc[sx]=0;while(!q.empty()) {nod nn=q.top();q.pop();if(book[nn.id])continue;book[nn.id]=1;if(nn.id==ex)break;for(int i=head[nn.id]; i!=-1; i=side[i].next) {int ty=side[i].id;if(dis[ty]>dis[nn.id]+side[i].d) {dis[ty]=dis[nn.id]+side[i].d;f[ty]=nn.id;if(cm>=num[ty]+tz[nn.id]) {tz[ty]=0;dc[ty]=dc[nn.id]+cm-(num[ty]+tz[nn.id]);} else {dc[ty]=dc[nn.id];tz[ty]=tz[nn.id]+num[ty]-cm;}q.push(nod(ty,dis[ty]));} else if(dis[ty]==dis[nn.id]+side[i].d) { // &&dc[ty]<if(cm>=num[ty]+tz[nn.id]) {if(dc[ty]>dc[nn.id]+cm-num[ty]+tz[nn.id]) {tz[ty]=0;dc[ty]=dc[nn.id]+cm-(num[ty]+tz[nn.id]);f[ty]=nn.id;q.push(nod(ty,dis[ty]));}} else {if(dc[ty]>dc[nn.id]) {dc[ty]=dc[nn.id];tz[ty]=tz[nn.id]+num[ty]-cm;f[ty]=nn.id;q.push(nod(ty,dis[ty]));}}} }}cout<<dc[ex]<<" ";printpath(ex);cout<<" "<<tz[ex]<<endl; }int main() {scanf("%d%d%d%d",&cmax,&n,&sp,&m);cm=cmax/2;int x,y,w;init();//初始化for(int i=1; i<=n; i++) {scanf("%d",&num[i]);}for(int i=0; i<m; i++) {scanf("%d%d%d",&x,&y,&w);add(x,y,w);add(y,x,w);}dijkstra(0,sp);return 0; }

總結(jié)：

? 這題不能用Dijkstra啊，因為在貪心的過程中只是dis數(shù)組是有效信息（頂多依據(jù)題意加一個最短路條數(shù)），其他的還有很多信息都丟失了。比如這組樣例，其中Cmax=10（也就是要湊5），第一個圈為PBMC，每個圈中的數(shù)字代表自行車數(shù);

如果最后一個圈內(nèi)數(shù)字是0，那么為①路徑，如果圈內(nèi)數(shù)字是5，那么為②路徑。所以具體哪個路徑還是要搜索去看，而不能DIjkstra就定終生。因為比如：在A這個點的時候，是①和②兩條路徑擇優(yōu)選擇了，沒問題，如果到此為止了肯定我們要②路徑。但是問題就在于，對于后面的點，未必會繼承這一特性啊！（以后自己造樣例的時候也可以這樣造，造一個樣例來說明不滿足“可繼承”特性的）換句話說這題的條件和需要加的限制很多，并無法證明滿足無后效性，所以會Dijkstra丟掉很多信息，而應(yīng)該用dfs，搜索每一條路徑，這樣就不會有漏下的情況。

? 讀到這里，我也是理解了前面那個“分析”中說的不能只用DIjkstra的原因。

總結(jié)

以上是生活随笔為你收集整理的【PAT - 甲级 - 1018】Public Bike Management （带权最短路，多条最短路中加条件，DFS）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。