b1001 Public Bike Management

タイトル:https://www.nowcoder.com/pat/5/problem/4324
タイトル:
車両管理システム.中心PBMC、Nサイト、Mエッジ、サイト最大容量Cがあり、各サイトに現在の駐車数があり、駐車数=S/2の場合、このサイトperfectを説明します.perfectではなく問題がある点です.今、指定された問題サイトに問題を解決するために、最適解を求めます(PBMCからサイトまでの時間が最も短く、時間が最も短い場合は、センターから車を送ったり回収したりする最小のポイントパスを選択します).
最初の行は、サイトの最大容量C、サイトの個数Nを与え、問題サイトの下付きラベルを指定し、M辺がある.
2行目、N駅停車数
3行目から最後まで、M辺
分析:
1、最短ルートを求め、単一ソース最短ルートSPFAを求め、最短ルートを求める
2.経路をDFSで比較し、最短経路の中から、センターが車両を発送または回収する最小の点経路を選択する
入力例:

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

コード:

#include 
#include 

using namespace std;

const int maxn = 501;
const int INF = 1000000000;

struct node
{
    int v,l;
    node(int _v,int _l):v(_v),l(_l){}
};
vector adj[maxn];
int bike[maxn];
int c,n,s,m;
vector pre[maxn];
int d[maxn];
int inq[maxn];
vector tempPath,path;
int sent = INF,take = INF;

void SPFA()
{
    queue q;
    for(int i=1;i<=n;i++)
    {
        d[i]=INF;
    }
    d[0]=0;
    q.push(0);
    inq[0]=1;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        inq[u]=0;
        for(int i=0;i=0;i--)
        {
            int u=tempPath[i];
            remain = remain+bike[u]-c/2;
            if(remain<0)
            {
                tempSent+=-remain;
                remain=0;
            }
        }
        if(tempSent=0;i--)
    {
        if(i");
        printf("%d",path[i]);
    }
    printf(" %d",take);

    return 0;
}