#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
long long plan_roller_coaster(vector<int> s, vector<int> t)
{
int n = s.size();
vector dis(n, vector<int>(n));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
dis[i][j] = max(0, t[i] - s[j]);
if (i == j)
dis[i][j] = 0;
}
vector dp(1 << n, vector<long long>(n, 1e18));
// for(int i = 0; i < n; i++)
// dp[1 << i][i] = 0;
dp[0][0] = 0;
for (int i = 0; i < (1 << n); i++)
for (int j = 0; j < n; j++)
if (dp[i][j] < 1e18)
for (int k = 0; k < n; k++)
if (!((i >> k) & 1))
{
dp[i | (1 << k)][k] = min(dp[i | (1 << k)][k], dp[i][j] + dis[j][k]);
}
long long res = 1e18;
for (int i = 0; i < n; i++)
res = min(res, dp[(1 << n) - 1][i]);
return res;
{
vector adj(n, vector<pair<int, long long>>());
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (i == j)
continue;
adj[i].push_back({j, max(0, t[i] - s[j])});
}
}
int cnt = 0;
vector<bool> vis(n, false);
long long mn = 1e18 + 10;
auto dfs = [&](auto self, int u, long long sum) -> void
{
if (vis[u])
{
return;
}
cnt++;
if (cnt == n)
{
if (mn > sum)
mn = sum;
cnt--;
return;
}
vis[u] = true;
for (auto [v, w] : adj[u])
{
if (not vis[v])
self(self, v, sum + w);
}
vis[u] = false;
cnt--;
};
for (int i = 0; i < n; i++)
{
dfs(dfs, i, 0ll);
}
return mn;
}
}
Compilation message (stderr)
railroad.h:1:9: warning: #pragma once in main file
1 | #pragma once
| ^~~~
railroad_c.h:1:9: warning: #pragma once in main file
1 | #pragma once
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |