2回答

liuyubobobo

2020-03-10

已采纳

抱歉，你给我的这个代码我提交以后编译不通过。我不确定是不是因为慕课网的编辑器有 bug。请尝试把代码编辑正确，或者在回答里放上完整能提交的代码。

=========

你读入数据应该先读入 n，再读入 tar。

cin>>capacity>>n>>tar>>m;

1

2

慕村0296978

感谢(❁´ω`❁)，感谢(❁´ω`❁)，感谢(❁´ω`❁)

2020-03-11

共2条回复

慕村0296978

提问者

2020-03-10

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

struct Node{

    int v;

    int w;

};

const int maxv = 510;

int capacity,tar,n,m;

const int inf = 0x3fffffff;

vector<Node> adj[maxv];//存储图

int visited[maxv] = {0};//标记顶点是否访问

int weight[maxv];//存储点权

int dis[maxv];//存储顶点的最短距离

vector<int> pre[maxv];//存储遍历出的最短路径树

//int road_num[540] = {0};//记录到达顶点的最短路径条数

vector<int> tempPath,path;//记录临时路径和最优路径

int min_need = inf,min_remain = inf;

void dijkstra(int s){

    fill(dis,dis+maxv,inf);

    dis[s] = 0;

    //pre[s].push_back(s);

    for(int i = 0;i<=n;i++){

        int u = -1,min_ = inf;

        for(int j = 0;j<=n;j++){

            if(dis[j] < min_ && visited[j] == 0){

                u = j;

                min_ = dis[j];

            }

        }

        if(u == -1) return;

        visited[u] = 1;

        for(int j = 0;j<adj[u].size();j++){

            int v = adj[u][j].v;

            int w = adj[u][j].w;

            if(visited[v] == 0){

                if(dis[u] + w < dis[v]){

                    dis[v] = dis[u] + w;

                    pre[v].clear();

                    pre[v].push_back(u);

                    //road_num[v] = road_num[u];

                }

                else if(dis[u] + w == dis[v]){

                    pre[v].push_back(u);

                    //road_num[v] += road_num[u];

                }

            }

        }

    }

}

void dfs(int v){

    if(v == 0){//如果当前路径到达PBM

        tempPath.push_back(v);

        int need = 0,remain = 0;//记录需要的值以及携带的值

        for(int i = tempPath.size()-1;i>=0;i--){

            int cur = tempPath[i];

            if(weight[cur] > 0){//当前车站有多余的

                remain += weight[cur];

            }

            else{

                if(abs(weight[cur]) < remain){//带有的足够

                    remain -= abs(weight[cur]);

                }

                else{

                    need += abs(weight[cur]) - remain;

                    remain = 0;

                }

            }

        }

//        for(int i = tempPath.size()-1;i>=0;i--){

//            cout<<tempPath[i];

//            if(i != 0)

//                cout<<"->";

//        }

//        cout<<endl;

        if(need < min_need){

            path = tempPath;

            min_need = need;

            min_remain = remain;

        }

        else if(need == min_need && remain < min_remain){

            path = tempPath;

            min_remain = remain;

        }

        //cout<<min_need<<" "<<min_remain<<endl;

        tempPath.pop_back();

        return;

    }

    tempPath.push_back(v);

    for(int i = 0;i<pre[v].size();i++){

        dfs(pre[v][i]);

    }

    tempPath.pop_back();

}

int main()

{

    cin>>capacity>>tar>>n>>m;

    for(int i = 1;i<=n;i++){

        cin>>weight[i]; weight[i] -= capacity/2;

    }

    int a,b,w;

    Node node;

    for(int i = 0;i<m;i++){

       cin>>a>>b>>w;

        node.v = b;node.w = w;

        adj[a].push_back(node);

        node.v = a;node.w = w;

        adj[b].push_back(node);

    }

    dijkstra(0);

    dfs(tar);

    cout<<min_need<<" ";

    for(int i = path.size()-1;i>=0;i--){

        cout<<path[i];

        if(i > 0)

            cout<<"->";

    }

    cout<<" "<<min_remain;

    return 0;

}

0

1

liuyubobobo

我在原回答上作了修改。

2020-03-11

共1条回复