題目

點(diǎn)存著自行車數(shù)，邊代表走的時(shí)間。PBMC是起點(diǎn)。
找最短路徑，time最小；如果time相等找攜帶bike最小的。
輸出：帶的bike數(shù) 0->s1->...->sp 帶回去的bike數(shù)（當(dāng)sp達(dá)到完美數(shù)后）

Sample Input

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

Sample Output

3 0->2->3 0

解法

法一：C++

思路：

最短路徑，Dijkstra算法

源代碼：

#include <iostream>
#include <cstdio>
#include <math.h>
#include <string.h>
#include <sstream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cctype>

using namespace std;
int cmax,n,sp,m;
int weight[505],e[505][505],dis[505];
bool visited[505]={false};
const int INF = 99999;

vector<int> pre[510], path, temppath;
int minNeed = INF, minBack = INF;
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() {
    //初始化
    fill(e[0], e[0] + 505 * 505, INF);
    fill(dis, dis + 505, INF);
    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;//直接減掉perfect condition
    }

    for(int i=0;i<m;i++){
        int temp1,temp2,t;
        scanf("%d %d %d",&temp1,&temp2,&t);
        e[temp1][temp2] = e[temp2][temp1] = t;
        
    }
    //for循環(huán)
    dis[0] = 0;
    for(int i=0;i<=n;i++){
        int u=-1,shortest = INF;
        for(int j=0;j<=n;j++){
            if(visited[j] == false && dis[j] < shortest){
                shortest = dis[j];
                u = j;
            }
        }
        if(u == -1) break;
        visited[u] = true;
        for(int v=0;v<=n;v++){
            if(visited[v] == false && e[u][v] != INF){
                if(dis[u]+e[u][v]<dis[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;
}

知識點(diǎn)+坑：

1.鞏固Dijkstra
2.學(xué)會DFS