$O({114514}^{114514^{114514^{114514^114514{114514^{114514}}}}})$
活动打卡代码
AcWing 849. Dijkstra求最短路 I
#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;
add(x, y, z);
}
cout << Dijkstra() << endl;
return 0;
}
活动打卡代码
AcWing 850. Dijkstra求最短路 II
#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;
add(x, y, z);
}
cout << Dijkstra() << endl;
return 0;
}
分享
线段树模板题
线段树
题目描述
如题，已知一个数列，你需要进行下面两种操作：
- 将某区间每一个数加上 $k$。
- 求出某区间每一个数的和。
输入格式
第一行包含两个整数 $n, m$，分别表示该数列数字的个数和操作的总个数。
第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。
接下来 $m$ 行每行包含 $3$ 或 $4$ 个整数，表示一个操作，具体如下：
1 x y k：将区间 $[x, y]$ 内每个数加上 $k$。2 x y：输出区间 $[x, y]$ 内每个数的和。
输出格式
输出包含若干行整数，即为所有操作 2 的结果。
样例 #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
提示
对于 $30\%$ 的数据：$n \le 8$，$m \le 10$。
对于 $70\%$ 的数据：$n \le {10}^3$，$m \le {10}^4$。
对于 $100\%$ 的数据：$1 \le n, m \le {10}^5$。
保证任意时刻数列中所有元素的绝对值之和 $\le {10}^{18}$。
【样例解释】
#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 asks(int r){
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);
return asks(lchild) + asks(rchild);
}
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)
cout << asks(1) << endl;
else{
cin >> k;
update(1,x,y);
}
}
return 0;
}
咕咕咕
