已经菜到板子都敲不熟练了 >_<。
敲板子前发现自己已经忘记快输怎么写了，没救了（笑哭）。
bfs板子
来自信奥一本通
（唉，还是喜欢手写队列...该改改了）
传送门
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int t,n,ax,ay,m,bx,by,head,tail;
char a[2025][2025];
int map1[201][201];
int dx[5]={0,1,-1,0,0};
int dy[5]={0,0,0,1,-1};
int d[999999][3];
void bfs(int x,int y ) {head=0,tail=1;d[1][1]=x;d[1][2]=y; d[1][3]=0; while (head<tail) { head++; for (int i=1;i<=4;i++) { int xx=d[head][1]+dx[i],yy=d[head][2]+dy[i]; if (xx>=1&&xx<=n&&yy>=1&&yy<=m&&map1[xx][yy]==0) { map1[xx][yy]=d[head][3]+1; tail++; d[tail][1]=xx;d[tail][2]=yy;d[tail][3]=map1[xx][yy]; }if (xx==bx&&yy==by) {cout<<map1[xx][yy]<<endl;return ;} } } cout<<"oop!"<<endl;
}
int main() {cin>>t;for (int k=1;k<=t;k++) {cin>>n>>m;memset(map1,0,sizeof(map1) ) ; for (int i=1;i<=n;i++) {for (int j=1;j<=m;j++) {cin>>a[i][j]; if (a[i][j]=='S') { ax=i,ay=j; } if (a[i][j]=='E') {bx=i;by=j; } if (a[i][j]=='#') map1[i][j]=1; } } bfs(ax,ay); }return 0;
}
单源最短路
来自洛谷
迪杰斯特拉都忘干净了，废了废了。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+2025;
int n,m,head[N],cnt,dis[N];
bool vis[N];
struct node{int next,to,w;
}e[N<<2];
void add(int u,int v,int w) {e[++cnt].next=head[u];e[cnt].to=v;e[cnt].w=w;head[u]=cnt;
}
void dj(int x) {priority_queue<int,vector<pair<int,int> >,greater<pair<int,int> > >q;memset(dis,0x3f,sizeof(dis));memset(vis,0,sizeof(vis));q.push(make_pair(0,x)); dis[x]=0;while(!q.empty()) {int now=q.top().second; q.pop();if (vis[now]) continue;vis[now]=1;for (int i=head[now];i;i=e[i].next) {if (dis[e[i].to]>dis[now]+e[i].w) {dis[e[i].to]=dis[now]+e[i].w;q.push(make_pair(dis[e[i].to],e[i].to));}}}
}
signed main() {int s;cin>>n>>m>>s;for (int i=1;i<=m;++i) {int x,y,z;cin>>x>>y>>z; add(x,y,z);}dj(s);for (int i=1;i<=n;++i) {cout<<dis[i]<<" ";}
}
加强版全源最短路
来自洛谷
要 spfa 处理重边自环，原来这题这么难吗
已经彻底退化了 >_<。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){int x=0,f=0;char ch=getchar();for(;!isdigit(ch);ch=getchar()) f|=(ch=='-');for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);return f?-x:x;
}
void print(int x) {if (x<0) putchar('-'),x=-x;if (x>9) print(x/10);putchar(x%10+48);
}
const int INF=1e9;
const int N=1e4+2025;
int n,m,cnt,head[N<<2],h[N],dis[N],t[N];
bool vis[N];
struct node{int next,to,w;
}e[N<<2];
void add(int u,int v,int w) {e[++cnt].next=head[u];e[cnt].to=v;e[cnt].w=w;head[u]=cnt;
}
bool spfa(int s){queue<int>q;memset(h,63,sizeof(h));h[s]=0;vis[s]=1; q.push(s);while(!q.empty()) {int now=q.front(); q.pop();vis[now]=0;for (int i=head[now];i;i=e[i].next) {if (h[e[i].to]>h[now]+e[i].w) {h[e[i].to]=h[now]+e[i].w;if (!vis[e[i].to]) {vis[e[i].to]=1;q.push(e[i].to);++t[e[i].to];if (t[e[i].to]==n+1) return 0;}}}}return 1;
}
void dj(int s) {priority_queue<int,vector<pair<int,int> >,greater<pair<int,int> > >q;for (int i=1;i<=n;++i) dis[i]=INF;memset(vis,0,sizeof(vis));q.push(make_pair(0,s)); dis[s]=0;while(!q.empty()) {int now=q.top().second; q.pop();if (vis[now]) continue;vis[now]=1;for (int i=head[now];i;i=e[i].next){if (dis[now]+e[i].w<dis[e[i].to]) {dis[e[i].to]=dis[now]+e[i].w;q.push(make_pair(dis[e[i].to],e[i].to));}}}
}
signed main(){n=read(); m=read();for (int i=1;i<=n;++i) {add(0,i,0);}for (int i=1;i<=m;++i) {int x=read(),y=read(),z=read();add(x,y,z);}if (!spfa(0)) {cout<<-1;return 0;}for (int now=1;now<=n;++now) {for (int i=head[now];i;i=e[i].next) {e[i].w+=h[now]-h[e[i].to];}}for (int i=1;i<=n;++i) {dj(i);int ans=0;for (int j=1;j<=n;++j) {if (dis[j]==INF) ans+=j*INF;else ans+=j*(dis[j]+h[j]-h[i]);}cout<<ans<<"\n";}return 0;
}
线段树
来自洛谷
终于有个还记得的了。
定义数组的时候习惯性的敲下 2023 ，真怀念啊。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {int x=0,f=0;char ch=getchar();for (;!isdigit(ch);ch=getchar()) f|=(ch=='-');for (;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);return f?-x:x;
}
void print(int x) {if (x<0) putchar('-'),x=-x;if (x>9) print(x/10);putchar(x%10+48);
}
const int N=1e6+2025;
int n,m,a[N];
namespace ss{#define lson pos<<1#define rson pos<<1|1struct node{int sum,len,lazy;}tree[N<<2];void push_up(int pos) {tree[pos].sum=tree[lson].sum+tree[rson].sum;}void build(int pos,int l,int r) {tree[pos].len=r-l+1;if (l==r) {tree[pos].sum=a[l];return ;}int mid=l+r>>1;build(lson,l,mid); build(rson,mid+1,r);push_up(pos);}void push_down(int pos) {if (!tree[pos].lazy) return ;tree[lson].sum+=tree[pos].lazy*tree[lson].len;tree[rson].sum+=tree[pos].lazy*tree[rson].len;tree[lson].lazy+=tree[pos].lazy;tree[rson].lazy+=tree[pos].lazy;tree[pos].lazy=0; return ;}void change(int pos,int l,int r,int L,int R,int k) {if (l>=L && r<=R) {tree[pos].sum+=k*tree[pos].len;tree[pos].lazy+=k;return ;}int mid=l+r>>1; push_down(pos);if (L<=mid) change(lson,l,mid,L,R,k);if (R>mid) change(rson,mid+1,r,L,R,k);push_up(pos);return ;}int query(int pos,int l,int r,int L,int R) {if (l>=L && r<=R) return tree[pos].sum;int mid=l+r>>1,res=0; push_down (pos);if (L<=mid) res+=query(lson,l,mid,L,R);if (R>mid) res+=query(rson,mid+1,r,L,R);return res;}
}
signed main(){n=read(); m=read();for (int i=1;i<=n;++i){a[i]=read();}ss::build(1,1,n);while(m--){int op=read(),x,y,z;if (op==1){x=read(); y=read(); z=read(); ss::change(1,1,n,x,y,z);}else {x=read(),y=read();cout<<ss::query(1,1,n,x,y)<<"\n";}}return 0;
}