1410

Jz_9

zyz529
lujunting
FBIFBIFBIFBIFBIFBIFBIFBIFBIFBI
--+

111yy66
Zrosor_Acw
SCP基金会

Chi
shaoyifan

LiyeeW
stamina_zeng

Colopen

1天前

1天前
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;
const int N = 500010, M = 200010, INF = 0x3f3f3f3f;
vector<int> q, p;
bool snt[6], tt[N];
int n, m, e[M], ne[M], h[N], idx, w[N], d[6][N], res = INF;
unordered_map<int, int> mp;

void add(int a, int b, int c){
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx ++;
}

void spfa(int x, int k){
memset(tt, 0, sizeof tt);
d[k][x] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> qu;
qu.push({0, x});
while(qu.size()){
auto value = qu.top();
qu.pop();
int val = value.second, dis = value.first;
if (tt[val]) continue;
tt[val] = true;
for (int i = h[val]; i != -1; i = ne[i]){
int t = e[i];
if (d[k][t] > dis + w[i]){
d[k][t] = dis + w[i];
qu.push({d[k][t], t});
}
}
}
}

void dfs(int sums, int pr, int num){
if (num == 5) {
res = min(res, sums);
return;
}
for (int i = 0; i < 5; i ++){
int k = p[i];
if (!snt[i]){
snt[i] = true;
dfs(sums + d[pr][k], mp[k]+1, num + 1);
snt[i] = false;
}
}
}

int main(){
cin >> n >> m;
memset(d, INF, sizeof d);
memset(h, -1, sizeof h);
for(int i = 0; i < 5; i ++) {
int x;
scanf("%d", &x);
p.push_back(x);
mp[x] = i;
}

for (int i = 0; i < m; i ++){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
}
spfa(1, 0);
for (int i = 0; i < 5; i ++) spfa(p[i], i+1);
dfs(0, 0, 0);
cout << res;
return 0;
}


3天前
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;
const int N = 20010, M = 10010;
int n, e[N], ne[N], h[M], idx, w[N];
int ans;
bool snt[M];

void add(int a, int b, int c){
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx ++;
}

int dfs(int val, int d){
bool falg = false;
int d1 = 0, d2 = 0, maxV = 0;
for (int i = h[val]; i != -1; i = ne[i]){
int k = e[i];
if (!snt[k]){
snt[k] = true;
falg = true;
int t = dfs(k, d) + w[i];
maxV = max(maxV, t);

if (t >= d1) d2 = d1, d1 = t;
else if (t >= d2) d2 = t;
snt[k] = false;
}
}

ans = max(ans, d1 + d2);
if (!falg) return d;
return maxV;

}

int main(){
cin >> n;
memset(h, -1, sizeof h);
for (int i = 0; i < n-1; i ++){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
}
snt[1] = true;
dfs(1, 0);
cout << ans;
return 0;
}


3天前

3天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 410;
int f[N][N], sums[N], a[N], q[N][N];

int main(){
int n;
cin >> n;
for (int i = 1; i <= n; i ++) {
scanf("%d", &a[i]);
sums[i] = a[i] + sums[i-1];
};

for (int i = n + 1; i <= 2 * n; i ++){
sums[i] = sums[i - 1] + a[i-n];
}

for (int i = 2; i <= 2 * n; i ++){
for (int l = 1; l <= 2 * n - i + 1; l ++){
int r = l + i - 1;
f[l][r] = 0x3f3f3f3f;
q[l][r] = 0;
for (int k = l; k < r; k ++){
f[l][r] = min(f[l][r], f[l][k] + f[k+1][r] + sums[r]-sums[l-1]);
q[l][r] = max(q[l][r], q[l][k] + q[k+1][r] + sums[r]-sums[l-1]);
}
}
}
int resMin = 0x3f3f3f3f, resMax = 0;
for (int i = 1; i < 2 * n - n + 1; i ++){
resMin = min(resMin, f[i][i + n - 1]);
resMax = max(resMax, q[i][i + n - 1]);
}
cout << resMin << endl;
cout << resMax;
return 0;
}


4天前
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>

using namespace std;
typedef pair<int, int> PR;
const int N = 14010, INF = 0x3f3f3f3f, M = 2510;
int e[N], ne[N], h[N], idx, w[N], n, c, start, es, dist[M];

void add(int a, int b, int c){
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx ++;
}

int dijstra(){
priority_queue<PR, vector<PR>, greater<PR>> qu;
memset(dist, INF, sizeof dist);
qu.push({0, start});
dist[start] = 0;
while(qu.size()){
auto x = qu.top();
qu.pop();
int val = x.second, dis = x.first;
if (val == es) return dis;
for (int i = h[val]; i != -1; i = ne[i]){
int k = e[i];
if (dis + w[i] < dist[k]){
dist[k] = dis + w[i];
qu.push({dis + w[i], k});
}
}
}
return dist[es];
}

int main(){
cin >> n >> c >> start >> es;
memset(h, -1, sizeof h);

for (int i = 0; i < c; i ++){
int rs, re, ci;
scanf("%d%d%d", &rs, &re, &ci);
}
cout << dijstra();
return 0;
}


4天前

5天前
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;
const int N = 12, M = 110, K = 1 << 10;
typedef long long LL;
LL f[N][M][K], n, k;
vector<int> state;
int cnt[K];

bool check(int x){
for (int i = 0; i <= x; i ++){
if (1 << i & x && 1 << (i+1) & x) return false;
}
return true;
}

int counts(int x){
int num = 0;
while(x) {
num ++;
x = (x-1) & x;
}
return num;
}

int main(){
cin >> n >> k;

for (int i = 0; i < 1 << n; i ++){
if (check(i)){
state.push_back(i);
cnt[i] = counts(i);
}
}
int len = state.size();
for (int i = 0; i < len; i ++){
for (int j = 0; j < len; j ++){
int a = state[i], b = state[j];
if ((a & b) == 0 && check(a | b)) {
}
}
}

f[0][0][0] = 1;
for (int i = 1; i <= n + 1; i ++) {
for (int j = 0; j <= k; j ++) {
for (int a = 0; a < state.size(); a ++){
int c = cnt[state[a]];
if (j >= c){
f[i][j][a] = (LL)f[i][j][a] + f[i-1][j - c][b];
}
}
}

}
}

cout << f[n+1][k][0];
return 0;
}


6天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 100010, M = 101, INF = 0x3f3f3f3f;
int dp[N][M][2];

int main(){
int n, k;
cin >> n >> k;

memset(dp, -INF, sizeof dp);
for (int i = 0; i <= n; i ++) dp[i][0][0] = 0;

for (int i = 1; i <= n; i ++){
int x;
scanf("%d", &x);
for (int j = 1; j <= k; j ++){
dp[i][j][0] = max(dp[i-1][j][1] + x, dp[i-1][j][0]);
dp[i][j][1] = max(dp[i-1][j-1][0] - x, dp[i-1][j][1]);
}
}

int res = 0;
for (int j = 0; j <= k; j ++){
res = max(res, dp[n][j][0]);
}
cout << res;
return 0;
}


6天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 100010;
int dp[N][2];

int main(){
int t;
cin >> t;

for (int i = 0; i < t; i ++){
int n;
scanf("%d", &n);
memset(dp, 0, sizeof dp);
for (int j = 1; j <= n; j ++){
int x;
scanf("%d", &x);
dp[j][0] = max(dp[j-1][0], dp[j-1][1]);
dp[j][1] = dp[j-1][0] + x;
}
printf("%d\n", max(dp[n][0], dp[n][1]));
}
return 0;
}