3.0万

yxh_0925

tonngw

xiami_ya
Errors

Scaramouche
xyzfrozen
Richard_H
M.z789
tyjz_yyds
Amy_Taylor

15小时前

$O({114514}^{114514^{114514^{114514^114514{114514^{114514}}}}})$

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

const int N = 150010;

typedef pair<int, int> PII;

int e[N],w[N],ne[N],h[N],dist[N],idx;
bool st[N];
int n,m;

void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int Dijkstra()
{
memset(dist,0x3f,sizeof dist);
dist[1]=0;
priority_queue<PII, vector<PII>, greater<PII> > heap;
heap.push({0,1});
while(heap.size()){
PII k=heap.top();
heap.pop();
int se=k.second,fi=k.first;
if(st[se]) continue;
st[se]=true;
for(int i=h[se];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j] > fi + w[i]){
dist[j]=fi+w[i];
heap.push({dist[j],j});
}
}
}
if(dist[n]==0x3f3f3f3f) return -1;
else return dist[n];
}

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

memset(h, -1, sizeof h);

while (m -- ){
int x,y,z;

cin >> x >> y >> z;

}

cout << Dijkstra() << endl;
return 0;
}


#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

const int N = 150010;

typedef pair<int, int> PII;

int e[N],w[N],ne[N],h[N],dist[N],idx;
bool st[N];
int n,m;

void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int Dijkstra()
{
memset(dist,0x3f,sizeof dist);
dist[1]=0;
priority_queue<PII, vector<PII>, greater<PII> > heap;
heap.push({0,1});
while(heap.size()){
PII k=heap.top();
heap.pop();
int se=k.second,fi=k.first;
if(st[se]) continue;
st[se]=true;
for(int i=h[se];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j] > fi + w[i]){
dist[j]=fi+w[i];
heap.push({dist[j],j});
}
}
}
if(dist[n]==0x3f3f3f3f) return -1;
else return dist[n];
}

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

memset(h, -1, sizeof h);

while (m -- ){
int x,y,z;

cin >> x >> y >> z;

}

cout << Dijkstra() << endl;
return 0;
}


18天前

18天前

19天前

20天前

# 线段树

## 题目描述

1. 将某区间每一个数加上 $k$。
2. 求出某区间每一个数的和。

## 输入格式

1. 1 x y k：将区间 $[x, y]$ 内每个数加上 $k$。
2. 2 x y：输出区间 $[x, y]$ 内每个数的和。

## 样例 #1

### 样例输入 #1

5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4


### 样例输出 #1

11
8
20


## 提示

【样例解释】

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define int long long

#define lchild (r << 1)
#define rchild ((r << 1) + 1)

const int N = 1e5 + 5;

struct node{
int lft,rgt,sum,lazy;
}seg_tree[N * 4];

int n,m,op,x,y,k,num[N];

void push_up(int r){

seg_tree[r].sum = seg_tree[lchild].sum + seg_tree[rchild].sum;

}

void build(int r,int st,int ed){

int Lft = st;

int Rgt = ed;

seg_tree[r].lft = Lft;

seg_tree[r].rgt = Rgt;

if (Lft == Rgt){

seg_tree[r].sum = num[Lft];

return;

}

int mid = (Lft + Rgt) / 2;

build(lchild,Lft,mid);

build(rchild,mid + 1,Rgt);

push_up(r);

}

void push_down(int r){

if (r * 2 + 1 >= 4 * n)
return;

seg_tree[lchild].lazy += seg_tree[r].lazy;

seg_tree[lchild].sum += (seg_tree[lchild].rgt - seg_tree[lchild].lft + 1) * seg_tree[r].lazy;

seg_tree[rchild].lazy += seg_tree[r].lazy;

seg_tree[rchild].sum += (seg_tree[rchild].rgt - seg_tree[rchild].lft + 1) * seg_tree[r].lazy;

seg_tree[r].lazy = 0;

}

int Lft = seg_tree[r].lft;
int Rgt = seg_tree[r].rgt;

if (y < Lft || Rgt < x)
return 0;

if (x <= Lft && Rgt <= y)
return seg_tree[r].sum;

if (seg_tree[r].lazy)
push_down(r);

}

void update(int r,int x,int y){

int Lft = seg_tree[r].lft;
int Rgt = seg_tree[r].rgt;

if (y < Lft || Rgt < x)
return;

if (x <= Lft && Rgt <= y){
seg_tree[r].lazy += k;
seg_tree[r].sum += (seg_tree[r].rgt - seg_tree[r].lft + 1) * k;
return;
}

if (seg_tree[r].lazy)
push_down(r);

update(lchild,x,y);

update(rchild,x,y);

push_up(r);

}

signed main(){

std::ios::sync_with_stdio(false);
cout.tie(0),cin.tie(0);

cin >> n >> m;

for(int i = 1;i <= n;i++)
cin >> num[i];

build(1,1,n);

while(m--){

cin >> op >> x >> y;

if (op == 2)

else{
cin >> k;
update(1,x,y);
}

}

return 0;

}



22天前
ACAPP在哪里下？

22天前
https://www.acwing.com/blog/content/31950/