数论 图论板子&&数据结构

时间：2022-11-01 15:55:18
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<functional>
#define LL long long
using namespace std;
inline int get_num()
{
    char c;
    int f=1,num=0;
    while((c=getchar())==' '||c=='\n'||c=='\r');
    if(c=='-') f=-1;
    else num=c-'0';
    while(isdigit(c=getchar())) num=num*10+c-'0';
    return num*f;
}
int main()
{
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);

    fclose(stdin);
    fclose(stdout);
    return 0;
}

1)线段树

inline void push_up(int p){
    tr[p].w=tr[p<<1].w+tr[p<<1|1].w;
}
inline void push_down(int p){
    if(!tr[p].lazy) return ;
    tr[p<<1].w+=tr[p].lazy*(tr[p<<1].r-tr[p<<1].l+1);
    tr[p<<1].lazy+=tr[p].lazy;
    tr[p<<1|1].w+=tr[p].lazy*(tr[p<<1|1].r-tr[p<<1|1].l+1);
    tr[p<<1|1].lazy+=tr[p].lazy;
    tr[p].lazy=0;
}
void build(int p,int l,int r){
    tr[p].l=l;tr[p].r=r;
    if(l==r){
        tr[p].w=get_num();
        return ;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid);build(p<<1|1,mid+1,r);
    push_up(p);
}
void add(int p,int l,int r,LL k){
    if(tr[p].l==l&&tr[p].r==r){
        tr[p].w+=(r-l+1)*k;
        tr[p].lazy+=k;
        return ;
    }
    push_down(p);
    int mid=(tr[p].r+tr[p].l)>>1;
    if(r<=mid) add(p<<1,l,r,k);
    else if(l>mid) add(p<<1|1,l,r,k);
    else{
        add(p<<1,l,mid,k);add(p<<1|1,mid+1,r,k);
    }
    push_up(p);

}
LL query(int p,int l,int r){
    if(tr[p].l==l&&tr[p].r==r){
        return tr[p].w;
    }
    LL ans=0;
    push_down(p);
    int mid=(tr[p].r+tr[p].l)>>1;
    if(r<=mid) ans=query(p<<1,l,r);
    else if(l>mid) ans=query(p<<1|1,l,r);
    else{
        ans=query(p<<1,l,mid)+query(p<<1|1,mid+1,r);
    }
    push_up(p);
    return ans;

}
int main()
{
    int n,m;n=get_num();m=get_num();
    build(1,1,n);
    int c,x,y;LL k;
    for(int i=1;i<=m;i++){
        c=get_num();x=get_num();y=get_num();
        if(c==1){
            k=get_num();
            add(1,x,y,k);
        }else{
            cout<<query(1,x,y)<<'\n';
        }
    }
    return 0;
}

2)树链剖分 

inline void push_up(int p){
    tr[p].w=tr[p<<1].w+tr[p<<1|1].w;
}
inline void push_down(int p){
    if(!tr[p].lazy) return ;
    tr[p<<1].w+=tr[p].lazy*(tr[p<<1].r-tr[p<<1].l+1);
    tr[p<<1].lazy+=tr[p].lazy;
    tr[p<<1|1].w+=tr[p].lazy*(tr[p<<1|1].r-tr[p<<1|1].l+1);
    tr[p<<1|1].lazy+=tr[p].lazy;
    tr[p].lazy=0;
}
void build(int p,int l,int r){
    tr[p].l=l;tr[p].r=r;
    if(l==r){
        tr[p].w=w[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    push_up(p);
}
void add(int p,int l,int r,LL k){
    if(tr[p].l==l&&tr[p].r==r)
    {
        tr[p].w+=(r-l+1)*k;
        tr[p].lazy+=k;
        return ;
    }
    push_down(p);
    int mid=(tr[p].l+tr[p].r)>>1;
    if(r<=mid) add(p<<1,l,r,k);
    else if(l>mid) add(p<<1|1,l,r,k);
    else{
        add(p<<1,l,mid,k);add(p<<1|1,mid+1,r,k);
    }
    push_up(p);
}
LL query(int p,int l,int r){
    if(tr[p].l==l&&tr[p].r==r)
    {
        return tr[p].w;
    }
    LL ans=0;
    push_down(p);
    int mid=(tr[p].l+tr[p].r)>>1;
    if(r<=mid) ans=query(p<<1,l,r);
    else if(l>mid) ans=query(p<<1|1,l,r);
    else{
        ans=query(p<<1,l,mid)+query(p<<1|1,mid+1,r);
    }
    push_up(p);
    return ans;
}
void dfs_1(int x){
    siz[x]=1;
    for(int i=0;i<v[x].size();i++){
        if(cur!=f[x]){
            f[cur]=x;
            deep[cur]=deep[x]+1;
            dfs_1(cur);
            siz[x]+=siz[cur];
            if(siz[son[x]]<siz[cur]) son[x]=cur;
        }
    }
}
void dfs_2(int x,int p){
    id[x]=++tot;w[tot]=d[x];top[x]=p;
    if(son[x]) dfs_2(son[x],p);
    for(int i=0;i<v[x].size();i++){
        if(cur!=f[x]&&cur!=son[x]){
            dfs_2(cur,cur);
        }
    }
}
void modify(int a,int b,int k){
    while(top[a]!=top[b]){
        if(deep[top[a]]>deep[top[b]]) swap(a,b);
        add(1,id[top[b]],id[b],k);
        b=f[top[b]];
    }if(deep[a]>deep[b]) swap(a,b);
    add(1,id[a],id[b],k);
}
LL find(int a,int b){
    LL ans=0;
    while(top[a]!=top[b]){
        if(deep[top[a]]>deep[top[b]]) swap(a,b);
        ans+=query(1,id[top[b]],id[b]); ans%=MOD;
        b=f[top[b]];
    }if(deep[a]>deep[b]) swap(a,b);
    ans+=query(1,id[a],id[b]);
    return ans%MOD;
}
int main()
{
    int n,m,root;
    n=get_num();m=get_num();root=get_num();MOD=get_num();
    for(int i=1;i<=n;i++) d[i]=get_num();
    for(int i=1;i<n;i++){
        int a,b;
        a=get_num();b=get_num();v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs_1(root);
    dfs_2(root,root);
    build(1,1,n);
    int c,x,y;LL z;
    for(int i=1;i<=m;i++){
        c=get_num();x=get_num();
        if(c==1){
            y=get_num();
            z=get_num();
            modify(x,y,z%MOD);
        }else if(c==2)
        {
            y=get_num();
            cout<<find(x,y)<<'\n';
        }else if(c==3){
            z=get_num();
            add(1,id[x],id[x]+siz[x]-1,z%MOD);
        }else if(c==4){
            cout<<query(1,id[x],id[x]+siz[x]-1)%MOD<<'\n';
        }
    }
    return 0;
}

3)最小生成树

bool cmp(const re &a,const re &b){
    return a.z<b.z;
}
int find(int x){
    if(f[x]==x) return x;
    return f[x]=find(f[x]);
}
int main()
{
    int n,m;n=get_num();m=get_num();
    for(int i=1;i<=m;i++){
        v[i].x=get_num();v[i].y=get_num();v[i].z=get_num();
    }
    sort(v+1,v+1+m,cmp);
    LL ans=0,cnt=0;
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=m;i++){
        if(find(v[i].x)!=find(v[i].y))
        {
            ++cnt; ans+=v[i].z;
            f[find(v[i].x)]=find(v[i].y);
            if(cnt==n-1){
                break;
            }
        }
    }
    if(cnt==n-1)cout<<ans;
    else cout<<"orz";
    return 0;
}

4)并查集

int find(int x){
    if(f[x]==x) return x;
    return f[x]=find(f[x]);
}

初始化 for(int i=1;i<=n;i++) f[i]=i;
5)树状数组2

void modify(int x,LL p){
    for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=p;
    //for和tr的i不要写错啊
}
LL query(int x){
    LL ans=0;
    for(int i=x;i;i-=lowbit(i)) ans+=tr[i];
    return ans;
}

modify(x,k);modify(y+1,-k);
写的 modify(x,k);modify(y+1,k);
for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=p;
写的 for(int i=x;i<=n;i+=lowbit(i)) tr[x]+=p;
6)树状数组 1
在全局有个n 主函数有个n 读入n的时候 全局相当于n是0
7)堆

priority_queue<int,vector<int>,greater<int> >Q;
    int n;n=get_num();
    int c,x;
    for(int i=1;i<=n;i++){
        c=get_num();
        if(c==1){
            x=get_num();
            Q.push(x);
        }else if(c==2){
            cout<<Q.top()<<'\n';
        }else {
            Q.pop();
        }
    }

8) 最近公共祖先（LCA）

void dfs(int x){
    vis[x]=1;
    for(int b=fa[x];b;b=v[b].nxt){
        if(!vis[cur])
        {
            deep[cur]=deep[x]+1;
            lca[cur][0]=x;
            dfs(cur);
        }
    }
}
int query(int a,int b)
{
    if(deep[a]>deep[b]) swap(a,b);
    for(int i=19;i>=0;i--) if(deep[lca[b][i]]>=deep[a]) b=lca[b][i];
    if(a==b) return a;
    for(int i=19;i>=0;i--){// 是大于等于0不是(int i=19;i;i--)
        if(lca[a][i]!=lca[b][i]){
            a=lca[a][i];b=lca[b][i];
        }
    }
    return lca[a][0];
}
    deep[s]=1;
    dfs(s);
    for(int j=1;j<=19;j++){
        for(int i=1;i<=n;i++){
            lca[i][j]=lca[lca[i][j-1]][j-1];
        }
    }

用 vector T 了俩点 还是好好用struct 吧
9) 最近公共祖先（tarjan）

void tarjan(int x){
    vis[x]=1;
    f[x]=x;
    for(int b=fa[x];b;b=v[b].nxt){
        if(!vis[cur]){
            tarjan(cur);
            f[find(cur)]=x;
        }
    }
    for(int b=faa[x];b;b=qv[b].nxt){
        if(vis[qv[b].to]){
            qv[b^1].ans=qv[b].ans=find(qv[b].to);
        }
    }
}

void add(int x,int y){
v[++p].to=y;
v[p].nxt=fa[x];
fa[x]=p;
}
v[++p].to=y;y写成了x

10) 最近公共祖先（树剖）

void dfs_1(int x){
    siz[x]=1;
    for(int b=fa[x];b;b=v[b].nxt){
        if(cur!=f[x]){
            f[cur]=x;
            deep[cur]=deep[x]+1;
            dfs_1(cur);
            siz[x]+=siz[cur];//忘写了一开始
            if(siz[son[x]]<siz[cur]) son[x]=cur;
        }
    }
}
void dfs_2(int x,int p){
    top[x]=p;
    if(son[x]) dfs_2(son[x],p);
    for(int b=fa[x];b;b=v[b].nxt){
        if(cur!=f[x]&&cur!=son[x]){
            dfs_2(cur,cur);
        }
    }
}
int query(int a,int b){
    while(top[a]!=top[b]){
        if(deep[top[a]]>deep[top[b]]) swap(a,b);
        b=f[top[b]];
    }
    return (deep[a]<=deep[b])? a : b;
}

dfs_1的时候
dfs_1(cur)后
忘记写：siz[x]+=siz[cur];
就相当于没有长长的链链了
就跳的很慢很慢了 然后就T了
其实常数是比LCA小的 OK的说
11) 三分法

int n;
double v[20];
double eps=1e-7;
double find(double x){ //find类型不要写错
    double ans=v[n+1];
    double p=1;
    for(int i=n;i;i--){
        p*=x;
        ans+=v[i]*p;
    }
    return ans;
}
int main()
{
    double l,r,mid,midd;
    cin>>n>>l>>r;
    for(int i=1;i<=n+1;i++) cin>>v[i];
    while(l+eps<=r){
        mid=(l+r)/2;
        midd=(l+mid)/2;
        if(find(midd)<find(mid)) l=midd;
        else r=mid;
    }
    printf("%.5lf",l);
    return 0;
}

double 类型 用的get_num()读进去了
其实应该用cin>>
能过样例也是奇迹

12) 最长公共子序列

    int n;n=get_num();
    for(int i=1;i<=n;i++) f[get_num()]=i;
    for(int i=1;i<=n;i++){
        int c=f[get_num()];
        if(c>dp[len]) dp[++len]=c;
        else{
            int l=1,r=len,mid;
            while(l<=r){
                mid=(l+r)>>1;
                if(dp[mid]>c) r=mid-1;
                else l=mid+1;
            }dp[l]=c;
        }       
    }
    cout<<len;

13)单源最短路径

    int n,m,s;n=get_num();m=get_num();s=get_num();
    for(int i=1;i<=m;i++){
        int a,b,c;
        a=get_num();b=get_num();c=get_num();
        add(a,b,c);//注意单项边还是双向边
    }
    for(int i=1;i<=n;i++) d[i]=2147483647;
    d[s]=0;
    vis[s]=1;//忘写了一开始
    Q.push(s);
    while(!Q.empty()){
        int h=Q.front();
        vis[h]=0;
        Q.pop();
        for(int b=fa[h];b;b=v[b].nxt)
        {
            if(d[cur]>d[h]+v[b].w)
            {
                d[cur]=d[h]+v[b].w;
                if(!vis[cur])
                {
                    vis[cur]=1;
                    Q.push(cur);
                }
            }
        }
    }

queue 里 vis[h]进来的时候 没有写vis[h]=0;

14)线性筛素数

    int n,m;n=get_num();m=get_num();
    for(int i=2;i<=n;i++){
        if(!vis[i]) pri[++cnt]=i;
        for(int j=1;j<=cnt&&pri[j]*i<=n;j++){
            vis[i*pri[j]]=1;//注意谁%谁 后者%不动
            if(i%pri[j]==0) break;
        }
    }
    vis[1]=1;//注意1首先啥都不是 其次他不是素数
    for(int i=1;i<=m;i++){
        if(vis[get_num()]) cout<<"No\n";
        else cout<<"Yes\n";
    }

没有考虑vis[1]=1的情况 详情看日记
15) 负环

void dfs(int x){
    if(ans) return ;
    vis[x]=1;
    for(int b=fa[x];b;b=v[b].nxt){
        if(d[cur]>d[x]+v[b].w){
            d[cur]=d[x]+v[b].w;
            if(vis[cur])
            {
                ans=1;
                break;
            }
            dfs(cur);
        }
    }
    vis[x]=0;
}
    while(t)
    {
        t--;int n,m;
        memset(vis,0,sizeof(vis));
        memset(d,0,sizeof(d));
        memset(fa,0,sizeof(fa));p=0;
        n=get_num();m=get_num();
        for(int i=1;i<=m;i++){
            int a,b,w;
            a=get_num();b=get_num();w=get_num();
            add(a,b,w);
            if(w>=0) add(b,a,w); 
        }
        ans=0;
        for(int i=1;i<=n;i++){
            dfs(i);
            if(ans) break;
        }
        if(ans) cout<<"YE5\n";
        else cout<<"N0\n";
    }

16)二分图匹配 再打一遍

int dfs(int x){
    for(int i=0;i<v[x].size();i++){
        if(!vis[cur])
        {
            vis[cur]=1;
            if(!match[cur]||dfs(match[cur]))
            {
                match[cur]=x;
                match[x]=cur;
                return 1;
            }
        }
    }
    return 0;
}
int n;
int query(){
    int ans=0;
    for(int i=1;i<=n;i++){
        if(!match[i]){
            memset(vis,0,sizeof(vis));
            if(dfs(i)) ans++;
        }
    }
    return ans;
}
int main()
{
    int m,e;n=get_num();m=get_num();e=get_num();
    for(int i=1;i<=e;i++){
        int a,b;a=get_num();b=get_num();
        if(b<=m) v[a].push_back(b+n);
    }
    cout<<query();
    return 0;
}

17)缩点 再打一遍

void tarjan(int x){
    my_s.push(x);in_s[x]=1;//注意不要忘了
    dfn[x]=low[x]=++tot;
    for(int b=fa[x];b;b=v[b].nxt){
        if(!dfn[cur]){
            tarjan(cur);
            low[x]=min(low[x],low[cur]);
        } else if(in_s[cur]) low[x]=min(low[x],dfn[cur]);
    }
    if(low[x]==dfn[x])
    {
        ++bcnt;
        while(my_s.top()!=x){
            fd[my_s.top()]=bcnt;d[bcnt]+=w[my_s.top()];in_s[my_s.top()]=0;my_s.pop();
        }
        d[bcnt]+=w[my_s.top()];fd[my_s.top()]=bcnt;in_s[my_s.top()]=0;my_s.pop();
    }
}

void build(){
    for(int i=1;i<=n;i++){
        for(int b=fa[i];b;b=v[b].nxt)
        {
            if(fd[i]!=fd[cur])
            {
                qv[fd[i]].push_back(fd[cur]);
            }
        }
    }
}
int dfs(int x){
    if(dp[x]) return dp[x];
    for(int i=0;i<qv[x].size();i++){
        dp[x]=max(dp[x],dfs(qv[x][i]));
    }
    dp[x]+=d[x];
    return dp[x];
}

———-
数论
18) 快速幂

LL fast_pow(LL a,LL p,LL k){
    LL ans=(a==0)?0:1;//注意是a不是p
    a%=k;
    for(;p;p>>=1,a=(a*a)%k)
    {
        if(p&1) ans=(ans*a)%k;
    }
    return ans;
}

19）gcd

int gcd(int a,int b)
{
    if(b==0) return a;
    return gcd(b,a%b);
}

20) exgcd 同余方程

void exgcd(LL a,LL b,LL &x,LL &y){
    if(b==0){
        x=1,y=0;return ;
    }
    exgcd(b,a%b,x,y);
    LL x2=x,y2=y;
    x=y2;y=x2-(a/b)*y2;//手推即可
}

21) 矩阵快速幂

struct matrix{
    LL n,m;
    LL v[110][110];
    matrix(){
        memset(v,0,sizeof(v));
    }
    void prinf(){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cout<<v[i][j]<<" ";
            }cout<<'\n';
        }
    }
};
matrix operator * (matrix a,matrix b){
    matrix res;res.n=b.n;res.m=a.m;
    for(int i=1;i<=res.n;i++){
        for(int j=1;j<=res.m;j++){
            for(int k=1;k<=a.n;k++){
                res.v[i][j]=(res.v[i][j]+a.v[k][j]*b.v[i][k])%MOD;
            }
        }
    }
    return res;
} 
inline LL get_num()
{
    char c;
    LL f=1,num=0;
    while((c=getchar())==' '||c=='\n'||c=='\r');
    if(c=='-') f=-1;
    else num=c-'0';
    while(isdigit(c=getchar())) num=num*10+c-'0';
    return num*f;
}
matrix fast_pow(matrix a,LL p){
    matrix ans;
    ans.n=a.n;ans.m=a.m;
    for(int i=1;i<=ans.n;i++) ans.v[i][i]=1;
    for(;p;p>>=1,a=(a*a))
    {
        if(p&1) ans=(ans*a);
    }return ans;
}
int main()
{
    LL n,k;
    matrix a;
    a.n=a.m=n=get_num();k=get_num();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            a.v[i][j]=(get_num())%MOD;
        }
    }
    fast_pow(a,k).prinf();
    return 0;
}

fast_pow 里面p>>=1 写的p>>1 get_num()没改LL

22)乘法逆元

    LL n,p;cin>>n>>p;
    inv[1]=1%p;cout<<inv[1]<<'\n';
    for(int i=2;i<=n;i++){
        inv[i]=(p-p/i)*inv[p%i]%p;//由p%i+(p/i)*i=p开始
        cout<<inv[i]<<'\n';
    }

割顶（割点）

void tarjan(int x){
    dfn[x]=low[x]=++tot;
    int rt=0;
    for(int b=fa[x];b;b=v[b].nxt){
        if(!dfn[cur]){
            rt++;
            f[cur]=f[x];
            tarjan(c            if(low[cur]>=dfn[x]&&f[x]!=x&&!vis[x]) vis[x]=1,ans++;//重要
        }else  low[x]=min(low[x],dfn[cur]);
    }
    if(f[x]==x&&rt>=2) ans++,vis[x]=1;
}

树上差分

LL fast_pow(LL a,LL p,LL k){
    LL ans=(a==0)?0:1;
    a%=k;
    for(;p;p>>=1,a=(a*a)%k)
    {
        if(p&1) ans=(ans*a)%k;
    }return ans;
}
int main()
{
    LL n,l,r;cin>>n>>l>>r;
    for(int i=1;i<=n;i++){
        v[i].m=get_num();v[i].a=get_num();
    }
    LL M=1;
    for(int i=1;i<=n;i++) M*=v[i].m;
    for(int i=1;i<=n;i++){
        v[i].M=M/v[i].m;
        v[i].k=fast_pow(v[i].M,v[i].m-2,v[i].m);
    }
    LL ans=0;
    for(int i=1;i<=n;i++) ans=(ans+v[i].a*v[i].M*v[i].k)%M;
    //cout<<ans;
    LL anss=0;
    if(r>=ans) anss=(r-ans)/M+1;
    if(l-1>=ans) anss-=(l-ans-1)/M+1;
    if(anss==0) cout<<0<<'\n'<<0;
    else{
        cout<<anss<<'\n';
        if(l-1>=ans){
            cout<<((l-1-ans)/M+1)*M+ans;
        }else cout<<ans;
    }
    return 0;
}

最大流量

const int maxn=50010;
struct re{
    int fd,to,nxt,ans;
}qv[maxn<<2];
vector<int> v[maxn];
int p=1,fa[maxn],vis[maxn],d[maxn],f[maxn],fath[maxn];int n,k;
inline void add(int x,int y){
    qv[++p].to=y;
    qv[p].nxt=fa[x];
    qv[p].fd=x;
    fa[x]=p;
}
inline int get_num()
{
    char c;
    int f=1,num=0;
    while((c=getchar())==' '||c=='\n'||c=='\r');
    if(c=='-') f=-1;
    else num=c-'0';
    while(isdigit(c=getchar())) num=num*10+c-'0';
    return num*f;
}
int find(int x){
    if(f[x]==x) return x;
    return f[x]=find(f[x]);
}
void tarjan(int x){
    vis[x]=1;
    f[x]=x;
    for(int i=0;i<v[x].size();i++){
        if(!vis[cur]){
            fath[cur]=x;
            tarjan(cur);
            f[find(cur)]=x;
        }
    }
    for(int b=fa[x];b;b=qv[b].nxt){
        if(vis[qv[b].to]){
            qv[b].ans=qv[b^1].ans=find(qv[b].to);
        }
    }
}
void dfs(int x){
    vis[x]=1;
    for(int i=0;i<v[x].size();i++){
        if(!vis[cur]){
            dfs(cur);
            d[x]+=d[cur]; 
        }
    }
}
int query(){
    for(int i=2;i<=p;i+=2){
        ++d[qv[i].fd];++d[qv[i].to];--d[qv[i].ans];
        --d[fath[qv[i].ans]];
    }
    memset(vis,0,sizeof(vis));
    dfs(1);
    int ans=0;
    for(int i=1;i<=n;i++){
        ans=max(ans,d[i]);
    }return ans;
}
int main()
{
    n=get_num();k=get_num();
    for(int i=1;i<n;i++){
        int a,b;a=get_num();b=get_num();
        v[a].push_back(b);v[b].push_back(a);
    }
    for(int i=1;i<=k;i++){
        int a,b;a=get_num();b=get_num();
        add(a,b);add(b,a);
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]) tarjan(i);
    }
    cout<<query();
    return 0;
}

Floyd

    int n;n=get_num();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            v[i][j]=get_num();
        }
    }for(int i=0;i<=n;i++) v[i][i]=0;
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                v[i][j]=min(v[i][j],v[i][k]+v[k][j]);
            }
        }
    }
    int m=get_num();
    for(int i=1;i<=m;i++){
        int a,b;a=get_num();b=get_num();
        cout<<v[a][b]<<'\n';
    }

堆优化dijkstra

struct re{
    int d,k;
};
struct cmp{
    inline bool operator () (re a, re b){
        return a.d>b.d;
    }
}; 
priority_queue<re,vector<re>,cmp >Q;
int main()
{
    int n,m;
    re s;
    n=get_num();m=get_num();s.k=get_num();
    for(int i=1;i<=m;i++){
        int a,b,c;a=get_num();b=get_num();c=get_num();
        add(a,b,c);
    }
    for(int i=1;i<=n;i++) d[i]=2147483647;
    d[s.k]=0;re B;s.d=0;
    Q.push(s);
    while(!Q.empty()){
        re h=Q.top();
        Q.pop();
        if(vis[h.k]) continue;
        vis[h.k]=1;
        for(int b=fa[h.k];b;b=v[b].nxt){
            if(d[cur]>d[h.k]+v[b].w){
                d[cur]=d[h.k]+v[b].w;
                B.d=d[cur];B.k=v[b].to;
                Q.push(B);
            }
        }
    }
    for(int i=1;i<=n;i++) cout<<d[i]<<" ";
    return 0;
}
标签：

相关文章