bjq

1.3万

Magneto
Jocelin
Self.

_Crush
kkkobe7
RHWFY
MIisaka
wbc-b
SalieriR
wscj
upczzh
TOT_Ysir

bjq
4天前
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;

const int N = 1010, M = 21010;
const int INF = 0x3f3f3f3f;
int n, m, T;
int h[N], e[M], w[M], ne[M], idx;
int d[N];
bool vis[N];

inline void add(int x, int y, int z) {
e[++idx] = y, w[idx] = z, ne[idx] = h[x], h[x] = idx;
}

inline void dijkstra(int node) {
priority_queue<PII, vector<PII>, greater<PII> > q;
q.push({0, node});
memset(vis, 0, sizeof(vis));
memset(d, 0x3f, sizeof(d));
d[node] = 0;
while (!q.empty()) {
int x = q.top().second; q.pop();
if (vis[x]) continue;
vis[x] = 1;
for (int i = h[x]; i; i = ne[i]) {
int y = e[i], z = w[i];
if (d[y] > d[x] + z) {
d[y] = d[x] + z;
q.push({d[y], y});
}
}
}
}

int main() {
while (cin >> n >> m >> T) {
memset(h, 0, sizeof(h));
idx = 0;
while (m--) {
int x, y, z;
cin >> x >> y >> z;
}
int s;
cin >> s;
while (s--) {
int ver;
cin >> ver;
}
dijkstra(0);
if (d[T] == INF) puts("-1");
else cout << d[T] << endl;
}

return 0;
}


bjq
4天前
#include <bits/stdc++.h>
using namespace std;

const int N = 100010, M = 2000010;
int n, m, price[N];
int h[N], rh[N], e[M], ne[M], idx;
int dmin[N], dmax[N];
bool vis[N];

inline void add(int *h, int x, int y) {
e[++idx] = y, ne[idx] = h[x], h[x] = idx;
}

inline void spfa(int *d, int st, int *h, bool flag) {
queue<int> q;
memset(vis, 0, sizeof(vis));
if (flag) memset(d, 0x3f, sizeof(dmin));
q.push(st);
vis[st] = 1;
d[st] = price[st];
while (!q.empty()) {
int x = q.front(); q.pop();
vis[x] = 0;
for (int i = h[x]; i; i = ne[i]) {
int y = e[i];
if (flag && d[y] > min(d[x], price[y]) || !flag && d[y] < max(d[x], price[y])) {
if (flag) d[y] = min(d[x], price[y]);
else d[y] = max(d[x], price[y]);
if (!vis[y]) {
vis[y] = 1;
q.push(y);
}
}
}
}
}

int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> price[i];
while (m--) {
int x, y, z;
cin >> x >> y >> z;
if (z == 2) add(h, y, x), add(rh, x, y);
}
spfa(dmin, 1, h, 1);
spfa(dmax, n, rh, 0);

int res = 0;
for (int i = 1; i <= n; i++)
res = max(res, dmax[i] - dmin[i]);
cout << res << endl;

return 0;
}


bjq
24天前
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;

const int N = 25010, M = 150010;
const int INF = 0x3f3f3f3f;
int n, mr, mp, s;
struct edge {
int y, z, ne;
} e[M];
int head[N], idx, id[N], d[N], bcnt, din[N];
vector<int> block[N];
bool vis[N];
queue<int> tq;

inline void add(int x, int y, int z) {
e[++idx] = {y, z, head[x]};
}

inline void dfs(int x, int bid) {
id[x] = bid;
block[bid].push_back(x);
for (int i = head[x]; i; i = e[i].ne) {
int y = e[i].y;
if (!id[y]) dfs(y, bid);
}
}

inline void dijkstra(int bid) {
priority_queue<PII, vector<PII>, greater<PII> > q;
for (int i = 0; i < block[bid].size(); i++)
q.push({d[block[bid][i]], block[bid][i]});
while (!q.empty()) {
int x = q.top().second; q.pop();
if (vis[x]) continue;
vis[x] = 1;
for (int i = head[x]; i; i = e[i].ne) {
int y = e[i].y, z = e[i].z;
if (d[y] > d[x] + z) {
d[y] = d[x] + z;
if (id[y] == id[x])
q.push({d[y], y});
}
if (id[y] != id[x] && --din[id[y]] == 0)
tq.push(id[y]);
}
}
}

inline void toposort() {
memset(d, 0x3f, sizeof(d));
d[s] = 0;
for (int i = 1; i <= bcnt; i++)
if (!din[i])
tq.push(i);
while (!tq.empty()) {
int u = tq.front(); tq.pop();
dijkstra(u);
}
}

int main() {
cin >> n >> mr >> mp >> s;
while (mr--) {
int x, y, z;
cin >> x >> y >> z;
}
for (int i = 1; i <= n; i++)
if (!id[i])
dfs(i, ++bcnt);
while (mp--) {
int x, y, z;
cin >> x >> y >> z;
din[id[y]]++;
}
toposort();
for (int i = 1; i <= n; i++)
if (d[i] > INF / 2) puts("NO PATH");
else cout << d[i] << endl;

return 0;
}



bjq
25天前
#include <bits/stdc++.h>
using namespace std;

const int N = 1010, M = 200010;
int n, m, k;
struct edge {
int y, z, ne;
} e[M];
int head[N], idx, d[N];
deque<int> q;
bool vis[N];

inline void add(int x, int y, int z) {
e[++idx] = {y, z, head[x]};
}

// BFS 01最短路
bool dijkstra(int maxw) {
memset(d, 0x3f, sizeof(d));
memset(vis, 0, sizeof(vis));
q.push_back(1);
d[1] = 0;
while (!q.empty()) {
int x = q.front(); q.pop_front();
if (vis[x]) continue;
vis[x] = 1;
for (int i = head[x]; i; i = e[i].ne) {
int y = e[i].y, z = (e[i].z > maxw);
if (d[y] > d[x] + z) {
d[y] = d[x] + z;
if (z) q.push_back(y);
else q.push_front(y);
}
}
}
return d[n] <= k;
}

int main() {
cin >> n >> m >> k;
while (m--) {
int x, y, z;
cin >> x >> y >> z;
}
int l = 0, r = 1e6 + 1;
while (l < r) {
int mid = l + r >> 1;
if (dijkstra(mid)) r = mid;
else l = mid + 1;
}
if (r == 1e6 + 1) puts("-1");
else cout << r << endl;

return 0;
}



bjq
1个月前
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;

const int N = 100010, M = 200010;
int h[N], e[M], ne[M], w[M], idx, n, m;
bool vis[N];
int d[6][N];
PII p[6];

inline void add(int x, int y, int z) {
e[++idx] = y, ne[idx] = h[x], h[x] = idx, w[idx] = z;
}

inline void dijkstra(int id) {
memset(vis, 0, sizeof(vis));
memset(d[id], 0x3f, sizeof(d[id]));
int node = p[id].second;
d[id][node] = 0;
priority_queue<PII, vector<PII>, greater<PII> > q;
q.push({0, node});
while (!q.empty()) {
int x = q.top().second; q.pop();
if (vis[x]) continue;
vis[x] = 1;
for (int i = h[x]; i; i = ne[i]) {
int y = e[i], z = w[i];
if (d[id][y] > d[id][x] + z) {
d[id][y] = d[id][x] + z;
q.push({d[id][y], y});
}
}
}
}

int main() {
cin >> n >> m;
p[0] = {0, 1};
for (int i = 1, pos; i < 6; i++) {
cin >> pos;
p[i] = {i, pos};
}
while (m--) {
int x, y, z;
cin >> x >> y >> z;
}
for (int i = 0; i < 6; i++)
dijkstra(i);
int ans = 0x3f3f3f3f;
do {
int res = 0;
for (int i = 0; i < 5; i++)
res += d[p[i].first][p[i + 1].second];
ans = min(ans, res);
} while (next_permutation(p + 1, p + 6));
cout << ans << endl;

return 0;
}



bjq
1个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 110, INF = 0x3f3f3f3f;
int n, m;
int w[N][N], lv[N];
int d[N];
bool vis[N];

inline int dijkstra(int minlv, int maxlv) {
memset(d, 0x3f, sizeof(d));
memset(vis, 0, sizeof(vis));
d[0] = 0;
for (int i = 1; i <= n + 1; i++) {
int t = -1;
for (int j = 0; j <= n; j++)
if (!vis[j] && (t == -1 || d[t] > d[j]))
t = j;
vis[t] = 1;
for (int j = 1; j <= n; j++)
if (lv[j] >= minlv && lv[j] <= maxlv)
d[j] = min(d[j], d[t] + w[t][j]);
}
return d[1];
}

int main() {
cin >> m >> n;
memset(w, 0x3f, sizeof(w));
for (int i = 1; i <= n; i++)
w[i][i] = 0;
for (int i = 1; i <= n; i++) {
int price, cnt;
cin >> price >> lv[i] >> cnt;
w[0][i] = min(price, w[0][i]);
while (cnt--) {
int id, cost;
cin >> id >> cost;
w[id][i] = min(w[id][i], cost);
}
}
int res = INF;
for (int i = lv[1] - m; i <= lv[i]; i++)
res = min(res, dijkstra(i, i + m));
cout << res << endl;

return 0;
}



bjq
2个月前
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 100010, M = N << 1;
int h[N], e[M], ne[M], w[M], idx, n, m;
int id[N], nw[N], cnt;
int dep[N], sz[N], top[N], fa[N], son[N];
struct tree {
int l, r;
} tr[N << 2];

inline int lc(int x) { return x << 1; }
inline int rc(int x) { return x << 1 | 1; }

inline void add(int x, int y) {
e[++idx] = y, ne[idx] = h[x], h[x] = idx;
}

inline void dfs1(int x, int f, int d) {
dep[x] = d, fa[x] = f, sz[x] = 1;
for (int i = h[x]; i; i = ne[i]) {
int y = e[i];
if (y == f) continue;
dfs1(y, x, d + 1);
sz[x] += sz[y];
if (sz[son[x]] < sz[y])
son[x] = y;
}
}

inline void dfs2(int x, int t) {
id[x] = ++cnt, nw[cnt] = w[x], top[x] = t;
if (!son[x]) return;
dfs2(son[x], t);
for (int i = h[x]; i; i = ne[i]) {
int y = e[i];
if (y == fa[x] || y == son[x]) continue;
dfs2(y, y);
}
}

inline void pushup(int x) {
tr[x].sum = tr[lc(x)].sum + tr[rc(x)].sum;
}

inline void pushdown(int x) {
ll &v = tr[x].add;
if (v) {
tr[lc(x)].sum += (tr[lc(x)].r - tr[lc(x)].l + 1) * v;
tr[rc(x)].sum += (tr[rc(x)].r - tr[rc(x)].l + 1) * v;
v = 0;
}
}

inline void build(int x, int l, int r) {
tr[x] = {l, r, 0, nw[r]};
if (l == r) return;
int mid = l + r >> 1;
build(lc(x), l, mid);
build(rc(x), mid + 1, r);
pushup(x);
}

inline void update(int x, int l, int r, ll v) {
if (l <= tr[x].l && tr[x].r <= r) {
tr[x].sum += v * (tr[x].r - tr[x].l + 1);
return;
}
pushdown(x);
int mid = tr[x].l  + tr[x].r >> 1;
if (l <= mid) update(lc(x), l, r, v);
if (r > mid) update(rc(x), l, r, v);
pushup(x);
}

inline ll query(int x, int l, int r) {
if (l <= tr[x].l && tr[x].r <= r)
return tr[x].sum;
pushdown(x);
int mid = tr[x].l + tr[x].r >> 1;
ll res = 0;
if (l <= mid) res += query(lc(x), l, r);
if (r > mid) res += query(rc(x), l, r);
return res;
}

inline void update_path(int x, int y, ll v) {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
update(1, id[top[x]], id[x], v);
x = fa[top[x]];
}
if (dep[x] < dep[y]) swap(x, y);
update(1, id[y], id[x], v);
}

inline ll query_path(int x, int y) {
ll res = 0;
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
res += query(1, id[top[x]], id[x]);
x = fa[top[x]];
}
if (dep[x] < dep[y]) swap(x, y);
res += query(1, id[y], id[x]);
return res;
}

inline void update_tree(int x, ll v) {
update(1, id[x], id[x] + sz[x] - 1, v);
}

inline ll query_tree(int x) {
return query(1, id[x], id[x] + sz[x] - 1);
}

int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> w[i];
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
}
dfs1(1, -1, 1);
dfs2(1, 1);
build(1, 1, n);
cin >> m;
while (m--) {
int op, u, v; ll k;
cin >> op >> u;
if (op == 1) {
cin >> v >> k;
update_path(u, v, k);
} else if (op == 2) {
cin >> k;
update_tree(u, k);
} else if (op == 3) {
cin >> v;
cout << query_path(u, v) << endl;
} else cout << query_tree(u) << endl;
}

return 0;
}



bjq
4个月前
#include <bits/stdc++.h>
using namespace std;

int main() {
int r, y, g;
int n, res = 0;
cin >> r >> y >> g >> n;
while (n--) {
int k, t;
cin >> k >> t;
if (!k) res += t;
else if (k == 1) res += t;
else if (k == 2) res += t + r;
}
cout << res << endl;

return 0;
}



bjq
4个月前
/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
auto dummy = new ListNode(-1);
auto a = dummy;
for (int i = 0; i < left - 1; i++) a = a->next;
auto b = a->next, c = b->next;
for (int i = 0; i < right - left; i++) {
auto d = c->next;
c->next = b;
b = c, c = d;
}
a->next->next = c;
a->next = b;
return dummy->next;
}
};


bjq
4个月前

Plan A

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
auto a = head, b =a->next;
while (b) {
auto c = b->next;
b->next = a;
a = b, b = c;
}
return a;
}
};


Plan B

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {