Kokaze

1828

Kokaze风

Kokaze
2022-05-05 16:59
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include<iostream>
#include<queue>
#include<algorithm>
#include<math.h>
#include<cstring>
#include<stack>
#include<vector>
#include<string>
#include<sstream>
using namespace std;

const int N = 50010, M = 200010, INF = 0x3f3f3f3f;
int h[N], e[M], ne[M], w[M], idx;
int source[7], dist[7][N];
int us[N],st[N];
int n, m;
typedef pair<int, int>PII;

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

void diji(int start,int id) {
memset(us, 0, sizeof us);
dist[id][start] = 0;
priority_queue<PII, vector<PII>, greater<PII>>heap;
heap.push({ 0,start });
while (heap.size()) {
auto t = heap.top();
heap.pop();
int ver = t.second,  dis = t.first;
if (us[ver] == 1)continue;
us[ver] = 1;
for (int i = h[ver]; i != -1; i = ne[i]) {
int j = e[i];
if (us[j] == 0 && dist[id][j] > dis + w[i]) {
dist[id][j] = dis + w[i];
heap.push({ dist[id][j],j });
}
}
}
}

int dfs(int u, int start, int distance) {
if (u == 6)return distance;

int res = INF;
for (int i = 1; i <= 5; i++) {
if (st[i] == 0) {
int next = source[i];
st[i] = 1;
res = min(res, dfs(u + 1, i, distance + dist[start][next]));
st[i] = 0;
}
}
return res;
}

int main() {
cin >> n >> m;
source[0] = 1;
for (int i = 1; i <= 5; i++)cin >> source[i];
memset(h, -1, sizeof h);
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
}
memset(dist, 0x3f, sizeof dist);
for (int i = 0; i < 6; i++)diji(source[i],i);

cout << dfs(1, 0, 0);

return 0;
}



Kokaze
2022-05-04 19:47
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include<iostream>
#include<queue>
#include<algorithm>
#include<math.h>
#include<cstring>
#include<stack>
#include<vector>
#include<string>
#include<sstream>
using namespace std;

const int N = 110;
int m, n;
int r[N];
int w[N][N];
int dist[N], st[N];

int diji(int lt, int rt) {
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof st);
dist[0] = 0;
for (int i = 0; i <= n; i++) {
int t = -1;
for (int j = 0; j <= n; j++) {
if (st[j] == 0 && (t == -1 || dist[j] < dist[t]))
t = j;
}
st[t] = 1;
for (int j = 1; j <= n; j++) {
if (r[j] >= lt && r[j] <= rt) {
dist[j] = min(dist[j], dist[t] + w[t][j]);
}
}

}
return dist[1];
}

int main() {
cin >> m >> n;
memset(w, 0x3f, sizeof w);
for (int i = 1; i <= n; i++) {
int price, num;
cin >> price >> r[i] >> num;
w[0][i] = min(price,w[0][i]);
for (int j = 1; j <= num; j++) {
int no, cost;
cin >> no >> cost;
w[no][i] = min(cost,w[no][i]);
}
}

int res = 0x3f3f3f3f;

for (int i = r[1] - m; i <= r[1]; i++)res = min(res, diji(i, i + m));

cout << res;

return 0;
}



Kokaze
2022-05-04 16:47
#include<iostream>
#include<queue>
#include<algorithm>
#include<math.h>
#include<cstring>
#include<stack>
#include<vector>
#include<string>
#include<sstream>
using namespace std;

const int N = 510;
int w[N][N];
int dist[N];
int m, n;
int stop[N];

void bfs() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
queue<int>q;
q.push(1);
while (q.size()) {
int t = q.front();
q.pop();
for (int i = 1; i <= n; i++) {
if (dist[i] == 0x3f3f3f3f && w[t][i]==1) {
q.push(i);
dist[i] = dist[t] + 1;
}
}
}
}

int main() {
cin >> m >> n;
string no_use;
getline(cin, no_use);
while (m--) {
string line;
getline(cin, line);
stringstream ssin(line);
int idx = 0, num;
while (ssin >> num)stop[idx++] = num;
for (int i = 0; i < idx; i++) {
for (int j = i+1; j < idx; j++) {
w[stop[i]][stop[j]] = 1;
}
}
}

bfs();
if (dist[n] == 0x3f3f3f3f)cout << "NO";
else cout << dist[n] - 1;
return 0;
}



Kokaze
2022-05-04 11:39
#include<iostream>
#include<queue>
#include<algorithm>
#include<math.h>
#include<cstring>
#include<stack>
#include<vector>
using namespace std;

const int N = 2010;
double w[N][N];
double dist[N];
int n, m;
int st[N];
int A, B;

double dj() {
dist[A] = 1;
for (int i = 1; i <= n; i++) {
int t = -1;
for (int j = 1; j <= n; j++) {
if (st[j] == 0 && (t == -1 || dist[j] > dist[t])) {
t = j;
}
}
st[t] = 1;
for (int i = 1; i <= n; i++) {
dist[i] = max(dist[i], dist[t] * w[t][i]);
}
}
return dist[B];
}

int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
w[a][b] = w[b][a] = max(w[a][b], (100.0-c)/100);
}

cin >> A >> B;

printf("%.8f", 100 / dj());

return 0;
}



Kokaze
2022-05-04 10:26
#include<iostream>
#include<queue>
#include<algorithm>
#include<math.h>
#include<cstring>
#include<stack>
#include<vector>
using namespace std;

const int N = 810, M = 3000;
int h[N], e[M], ne[M], w[M], idx;
int dist[N], st[N];
int id[M];
int n, p, c;
const int INF = 0x3f3f3f3f;

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

int spfa(int start) {
memset(dist, 0x3f, sizeof dist);
st[start] = 1;
queue<int>q;
dist[start] = 0;
q.push(start);
while (q.size()) {
int t = q.front();
q.pop();
st[t] = 0;
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
if (st[j] == 0) {
q.push(j);
st[j] = 1;
}
}
}
}

int res = 0;
for (int i = 1; i <= n; i++) {
int t = id[i];
if (dist[t] == INF) {
res = INF;
return INF;
}
else {
res += dist[t];
}
}
return res;
}

int main() {
cin >> n >> p >> c;
for (int i = 1; i <= n; i++)cin >> id[i];

memset(h, -1, sizeof h);

for (int i = 0; i < c; i++) {
int aa, bb, cc;
cin >> aa >> bb >> cc;
}

int res = INF;
for (int i = 1; i <= p; i++) {
res = min(res, spfa(i));
}
cout << res;
return 0;
}



Kokaze
2022-05-04 09:55
#include<iostream>
#include<queue>
#include<algorithm>
#include<math.h>
#include<cstring>
#include<stack>
#include<vector>
using namespace std;

const int N = 105;
int dist[N][N];
int n, m;

int main() {
cin >> n >> m;
memset(dist, 0x3f, sizeof dist);
for (int i = 1; i <= n; i ++ ) dist[i][i] = 0;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
dist[a][b] = dist[b][a] = min(dist[a][b], c);
}

for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
int res = 0;
for (int i = 1; i <= n; i++) {
if (dist[1][i] == 0x3f3f3f3f) {
res = -1;
break;
}
else res = max(res, dist[1][i]);
}
cout << res;
return 0;
}



Kokaze
2022-05-04 09:15
#include<iostream>
#include<queue>
#include<algorithm>
#include<math.h>
#include<cstring>
#include<stack>
#include<vector>
using namespace std;

const int N = 2510, M = 12410;
int T, C, Ts, Te;
int h[N], e[M], ne[M], w[M], idx;
int dist[N], st[N];

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

void spfa() {
memset(dist, 0x3f, sizeof dist);
queue<int>q;
dist[Ts] = 0;
st[Ts] = 1;
q.push(Ts);
while (q.size()) {
int t = q.front();
q.pop();
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
if (st[j] == 0) {
q.push(j);
}
}
}
}
}

int main() {
cin >> T >> C >> Ts >> Te;
memset(h, -1, sizeof h);
for (int i = 0; i < C; i++) {
int a, b, c;
cin >> a >> b >> c;
}
spfa();
cout << dist[Te];
return 0;
}



Kokaze
2022-05-03 16:08
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include<iostream>
#include<queue>
#include<algorithm>
#include<math.h>
#include<cstring>
#include<stack>
#include<vector>
using namespace std;

const int N = 104*2;
int w[N];
int f[N][N];
int n;

int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> w[i];
w[n + i] = w[i];
}

for (int len = 3; len <= n + 1; len++) {
for (int l = 1; l + len - 1 <= 2 * n; l++) {
int r = l + len - 1;
for (int k = l + 1; k < r; k++) {
f[l][r] = max(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]);
}
}
}
int maxv = -0x3f3f3f3f;

for (int i = 1; i <= n; i++) {
int j = i + n;
maxv = max(maxv, f[i][j]);
}
cout << maxv;
return 0;
}



Kokaze
2022-05-03 12:28

# include[HTML_REMOVED]

using namespace std;

const int N = 405;
int f1[N][N], f2[N][N];
int w[N];
int s[N];
int n;
const int INF = 0x3f3f3f3f;

int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> w[i];
w[i + n] = w[i];
}

for (int i = 1; i <= 2 * n; i++)s[i] = s[i - 1] + w[i];

memset(f1, 0x3f, sizeof f1);
memset(f2, -0x3f, sizeof f2);

for (int len = 1; len <= n; len++) {
for (int l = 1; l + len - 1 <= 2 * n; l++) {
int r = l + len - 1;
if (len == 1)f1[l][r] = f2[l][r] = 0;
else {
for (int k = l; k < r; k++) {
f1[l][r] = min(f1[l][r], f1[l][k] + f1[k + 1][r] + s[r] - s[l - 1]);
f2[l][r] = max(f2[l][r], f2[l][k] + f2[k + 1][r] + s[r] - s[l - 1]);
}
}
}
}
int maxv = -INF, minv = INF;
for (int i = 1; i <= n; i++) {
maxv = max(maxv, f2[i][i + n - 1]);
minv = min(minv, f1[i][i + n - 1]);
}
cout << minv << endl << maxv;

return 0;


}



Kokaze
2022-05-03 10:53
#include<iostream>
#include<queue>
#include<algorithm>
#include<math.h>
#include<cstring>
#include<stack>
#include<vector>
using namespace std;

const int N = 18;
int s[N][N];
int f[1 << N];
int t, n, m, no_use;
typedef pair<double, double> PDD;
PDD d[N];
const double dlt = 1e-6;
int cmp(double a, double b) {
if (abs(a - b) < dlt)return 0;
if (a - b < 0)return -1;
return 1;
}

int main() {
cin >> t;
while (t--) {
cin >> n >> no_use;
for (int i = 0; i < n; i++)cin >> d[i].first >> d[i].second;
memset(s, 0, sizeof s);
memset(f, 0x3f, sizeof f);
for (int i = 0; i < n; i++) {
s[i][i] = 1 << i;
for (int j = 0; j < n; j++) {
double x1 = d[i].first, y1 = d[i].second;
double x2 = d[j].first, y2 = d[j].second;
if (cmp(x1, x2) == 0)continue;
double a = (y1 / x1 - y2 / x2) / (x1 - x2);
double b = y1 / x1 - a * x1;
if (cmp(a,0) >= 0)continue;

for (int k = 0; k < n; k++) {
if (cmp(a * d[k].first * d[k].first + b * d[k].first, d[k].second) == 0) {
s[i][j] += 1 << k;
}
}
}
}
f[0] = 0;
for (int i = 0; i < (1 << n) - 1; i++) {
int x = 0;
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) == 0)x = j;
}

for (int j = 0; j < n; j++) {
f[i | s[x][j]] = min(f[i | s[x][j]], f[i] + 1);
}
}
cout << f[(1 << n) - 1] << endl;

}
return 0;
}

`