798236606 发表于 2020-2-26 12:55:09

PTA A_1018 Public Bike Management

传送门：https://pintia.cn/problem-sets/994805342720868352/problems/994805489282433024

解：
迪杰斯特拉+DFS（模板）
#include <cstdio>
#include <climits>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

const int maxn = 510;

int c_max, n, sp, m;
int pw;
int d;
bool vis;
int G;
vector<int> pre;

void DJS(void)
{
    fill(d, d + maxn, INT_MAX);
    memset(vis, false, sizeof(vis));

    d = 0;

    for (int i = 0; i < n; i++)
    {
      int u= -1, min = INT_MAX;

      for (int j = 0; j <= n; j++)
            if (!vis && d < min) min = d;

      if (u == -1) return;

      vis = true;

      for (int v = 1; v <= n; v++)
      {
            if (vis || G == INT_MAX) continue;

            if (G + d < d)
            {
                d = G + d;
                pre.clear();
                pre.push_back(u);
            }
            else if (G + d == d)
                pre.push_back(u);
      }
    }
}

vector<int> path, temp_path;
int send = INT_MAX, back = INT_MAX;

void DFS(int id)
{
    if (!id)
    {
      int sen = 0, bac = 0;

      for (int i = temp_path.size() - 1; i >= 0; i--)
      {
            bac += pw];

            if (bac < 0)
            {
                sen -= bac;
                bac = 0;
            }
      }

      if (sen < send || (sen == send && bac < back))
      {
            path = temp_path;
            send = sen;
            back = bac;
      }
    }

    temp_path.push_back(id);

    for (int i = 0; i < pre.size(); i++)
      DFS(pre);
   
    temp_path.pop_back();
}

int main(void)
{
    // freopen("input.txt", "r", stdin);
    scanf("%d %d %d %d", &c_max, &n, &sp, &m);

    for (int i = 1; i <= n; i++)
    {
      scanf("%d", pw + i);
      pw -= c_max / 2;
    }
      
    fill(G, G + maxn * maxn, INT_MAX);
   
    while (m--)
    {
      int a, b, l;
      scanf("%d %d %d", &a, &b, &l);

      G = G = l;
    }

    DJS();
    DFS(sp);

    printf("%d 0", send);
    for (int i = path.size() - 1; i >= 0; i--)
      printf("->%d", path);

    printf(" %d", back);

    return 0;
}
页: [1]
查看完整版本: PTA A_1018 Public Bike Management