C++ 模板

1. 差分模板

#include <bits/stdc++.h>
using namespace std;
int n,k,data[1000010],diff[1000010],a[1000010];
int main()
{
    int a,b,v=0;
    int x;
    cin>>n>>k;
    for(int i=1;i<=n;i++) {
        cin>>a[i]; if(i==1) diff[i]=a[i]; else diff[i]=a[i]-a[i-1]
    }
    for (int i=0;i<k;++i) {
        cin>>a>>b>>x;
        diff[a]+=x;
        diff[b+1]-=x;
    }
    for (int i=1;i<=n;++i) {
        v+=diff[i];
        data[i]=v;
    }
    return 0;
}

2. 高精度模板

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int maxn = 10000;
const int BIT = 4;
const int MOD = 1e4;

struct bign {
    int num[maxn], len;
    bool flag;

    friend bign abs(const bign &x) {
        bign k = x;
        k.flag = true;
        return k;
    }

    friend void remove(bign &x) {
        while (x.num[x.len] == 0 && x.len > 1)x.len--;
    }

    bign() {
        memset(num, 0, sizeof(num));
        flag = true;
        len = 1;
    }

    bign(const int &x) {
        *this = bign();
        if (x) {
            int k = x;
            if (k < 0)k = -k, flag = false;
            len = 0;
            while (k) {
                num[++len] = k % MOD;
                k /= MOD;
            }
        }
    }

    bign(const ll &x) {
        *this = bign();
        if (x) {
            ll k = x;
            if (k < 0)k = -k, flag = false;
            len = 0;
            while (k) {
                num[++len] = k % MOD;
                k /= MOD;
            }
        }
    }

    bign(const char *x) {
        int l = strlen(x), s, t = 0, p = 0, k = 1;
        *this = bign();
        if (x[0] == '-')flag = false, s = 1;
        len = 0;
        for (int i = l - 1; i >= s; i--) {
            p += k * (x[i] - '0');
            k *= 10;
            t++;
            if (t == 4) {
                t = 0;
                num[++len] = p;
                p = 0;
                k = 1;
            }
        }
        if (p)num[++len] = p;
    }

    bign(const string x) {
        int l = x.length(), s = 0, t = 0, p = 0, k = 1;
        *this = bign();
        if (x[0] == '-')flag = false, s = 1;
        len = 0;
        for (int i = l - 1; i >= s; i--) {
            p += k * (x[i] - '0');
            k *= 10;
            t++;
            if (t == BIT) {
                t = 0;
                num[++len] = p;
                p = 0;
                k = 1;
            }
        }
        if (p)num[++len] = p;
    }

    bign operator=(const int &x) {
        return *this = bign(x);
    }

    bign operator=(const ll &x) {
        return *this = bign(x);
    }

    bign operator=(const char *x) {
        return *this = bign(x);
    }

    bign operator=(const string &x) {
        return *this = bign(x);
    }

    bool operator<(const bign &x) const {
        if (flag != x.flag)return flag < x.flag;
        if (len != x.len)return (len < x.len) ^ flag ^ 1;
        for (int i = len; i >= 1; i--) {
            if (num[i] != x.num[i]) {
                return (num[i] < x.num[i]) ^ flag ^ 1;
            }
        }
        return false;
    }

    bool operator<(const int &x) const {
        return *this < bign(x);
    }

    bool operator<(const ll &x) const {
        return *this < bign(x);
    }

    bool operator>(const bign &x) const {
        return x < *this;
    }

    bool operator>(const int &x) const {
        return *this > bign(x);
    }

    bool operator>(const ll &x) const {
        return *this > bign(x);
    }

    bool operator<=(const bign &x) const {
        return !(*this > x);
    }

    bool operator<=(const int &x) const {
        return *this <= bign(x);
    }

    bool operator<=(const ll &x) const {
        return *this <= bign(x);
    }

    bool operator>=(const bign &x) const {
        return !(*this < x);
    }

    bool operator>=(const int &x) const {
        return *this >= bign(x);
    }

    bool operator>=(const ll &x) const {
        return *this >= bign(x);
    }

    bool operator==(const bign &x) const {
        if (flag != x.flag)return false;
        if (len != x.len)return false;
        for (int i = len; i >= 1; i--) {
            if (num[i] != x.num[i]) {
                return false;
            }
        }
        return true;
    }

    bool operator==(const int &x) const {
        return *this == bign(x);
    }

    bool operator==(const ll &x) const {
        return *this == bign(x);
    }

    bool operator!=(const bign &x) const {
        return !(*this == x);
    }

    bool operator!=(const int &x) const {
        return *this != bign(x);
    }

    bool operator!=(const ll &x) const {
        return *this != bign(x);
    }

    friend istream &operator>>(istream &in, bign &x) {
        string s;
        in >> s;
        x = s;
        return in;
    }

    friend ostream &operator<<(ostream &out, const bign &x) {
        if (x.flag == false && x != 0)out << "-";
        out << x.num[x.len];
        for (int i = x.len - 1; i >= 1; i--)printf("%0*d", BIT, x.num[i]);
        return out;
    }

    bign operator-() const {
        bign k = *this;
        k.flag ^= 1;
        return k;
    }

    bign operator+(const bign &x) const {
        if (flag && x.flag) {
            bign k = bign();
            k.len = 0;
            for (int i = 1, g = 0; g || i <= len || i <= x.len; i++) {
                int p = num[i] + x.num[i] + g;
                k.num[++k.len] = p % MOD;
                g = p / MOD;
            }
            return k;
        }
        if (flag && !x.flag)return *this - (-x);
        if (!flag && x.flag)return x - (-*this);
        return -((-x) + (-*this));
    }

    bign operator+(const int &x) const {
        return *this + bign(x);
    }

    bign operator+=(const bign &x) {
        return *this = *this + x;
    }

    bign operator+=(const int &x) {
        return *this += bign(x);
    }

    bign operator+=(const ll &x) {
        return *this += bign(x);
    }

    bign operator++() {
        return *this += 1;
    }

    bign operator++(int) {
        bign k = *this;
        *this += 1;
        return k;
    }

    bign operator-(const bign &x) const {
        if (flag && x.flag && *this >= x) {
            bign k = bign();
            k.len = 0;
            for (int i = 1, g = 0; g || i <= len; i++) {
                int p = num[i] - x.num[i] + g;
                if (p < 0)g = -1;
                else g = 0;
                k.num[++k.len] = (p % MOD + MOD) % MOD;
            }
            remove(k);
            return k;
        }
        if (flag && x.flag)return -(x - *this);
        if (flag && !x.flag)return *this + (-x);
        if (!flag && x.flag)return -((-*this) + x);
        return (-x) - (-*this);
    }

    bign operator-=(const bign &x) {
        *this = *this - x;
        return *this;
    }

    bign operator-=(const int &x) {
        return *this -= bign(x);
    }

    bign operator-=(const ll &x) {
        return *this -= bign(x);
    }

    bign operator--() {
        return *this -= 1;
    }

    bign operator--(int) {
        bign k = *this;
        *this -= 1;
        return k;
    }

    bign operator*(const bign &x) const {
        bign k;
        k.flag = (flag == x.flag);
        k.len = len + x.len + 1;
        for (int i = 1; i <= len; i++) {
            for (int j = 1; j <= x.len; j++) {
                k.num[i + j - 1] += num[i] * x.num[j];
                k.num[i + j] += k.num[i + j - 1] / MOD;
                k.num[i + j - 1] %= MOD;
            }
        }
        remove(k);
        return k;
    }

    bign operator*(const int &x) const {
        bign k = bign();
        k.len = 0;
        long long t[maxn];
        memset(t, 0, sizeof(t));
        for (int i = 1; i <= len; i++)t[i] = num[i] * x;
        for (int i = 1, g = 0; i <= len || g; i++) {
            k.num[++k.len] = (g + t[i]) % MOD;
            g = (g + t[i]) / MOD;
        }
        return k;
    }

    bign operator*(const ll &x) const {
        bign k = bign();
        k.len = 0;
        long long t[maxn];
        memset(t, 0, sizeof(t));
        for (int i = 1; i <= len; i++)t[i] = num[i] * x;
        for (int i = 1, g = 0; i <= len || g; i++) {
            k.num[++k.len] = (g + t[i]) % MOD;
            g = (g + t[i]) / MOD;
        }
        return k;
    }

    bign operator*=(const bign &x) {
        return *this = *this * x;
    }

    bign operator*=(const int &x) {
        return *this = *this * x;
    }

    bign operator*=(const ll &x) {
        return *this = *this * x;
    }

    bign operator/(const bign &x) const {
        if (x == 0)return bign();
        bign k = bign(), a = bign();
        k.flag = (flag == x.flag);
        k.len = len;
        for (int i = len; i >= 1; i--) {
            a = a * MOD + num[i];
            while (a >= abs(x)) {
                a -= abs(x);
                k.num[i]++;
            }
        }
//        if ((flag != x.flag) & a != 0)
//            k--;  //取模
        remove(k);
        return k;
    }

    bign operator/(const int &x) const {
        if (x == 0)return bign();
        bign k = bign();
        int a = 0;
        k.flag = (flag == (x >= 0));
        k.len = len;
        for (int i = len; i >= 1; i--) {
            a = a * MOD + num[i];
            k.num[i] = a / x;
            a %= x;
        }
//        if ((flag != x.flag) & a != 0)
//            k--;  //取模
        remove(k);
        return k;
    }

    bign operator/(const ll &x) const {
        if (x == 0)return bign();
        bign k = bign();
        int a = 0;
        k.flag = (flag == (x >= 0));
        k.len = len;
        for (int i = len; i >= 1; i--) {
            a = a * MOD + num[i];
            k.num[i] = a / x;
            a %= x;
        }
//        if ((flag != x.flag) & a != 0)
//            k--;  //取模
        remove(k);
        return k;
    }

    bign operator/=(const bign &x) {
        return *this = *this / x;
    }

    bign operator/=(const int &x) {
        return *this = *this / x;
    }

    bign operator/=(const ll &x) {
        return *this = *this / x;
    }

    bign operator%(const bign &x) const {
        if (x == 0)return bign();
        bign a = bign();
        for (int i = len; i >= 1; i--) {
            a = a * MOD + num[i];
            while (a >= abs(x))a -= abs(x);
        }
//        if (a == 0)return a;
//        if (flag && x.flag)return a;
//        if (flag && !x.flag)return a + x;
//        if (!flag && x.flag)return x - a;
//        return -a;//取模
        if (flag)return a;
        return -a;
    }

    bign operator%(const int &x) const {
        return *this % bign(x);
    }

    bign operator%(const ll &x) const {
        return *this % bign(x);
    }

    bign operator%=(const bign &x) {
        return *this = *this % x;
    }

    bign operator%=(const int &x) {
        return *this %= bign(x);
    }

    bign operator%=(const ll &x) {
        return *this %= bign(x);
    }

    friend bign pow(const bign &x, const bign &y) {
        bign ans = 1, cnt = x, w = y;
        while (w > 0) {
            if (w % 2 == 1)ans *= cnt;
            cnt *= cnt;
            w /= 2;
        }
        return ans;
    }

    friend bign pow(const int &x, const bign &y) {
        bign ans = 1, cnt = x, w = y;
        while (w > 0) {
            if (w % 2 == 1)ans *= cnt;
            cnt *= cnt;
            w /= 2;
        }
        return ans;
    }

    friend bign pow(const bign &x, const int &y) {
        bign ans = 1, cnt = x;
        int w = y;
        while (w) {
            if (w & 1)ans *= cnt;
            cnt *= cnt;
            w >>= 1;
        }
        return ans;
    }

    friend bign powmod(const bign &x, const bign &y, const bign &z) {
        bign ans = 1, cnt = x, w = y;
        while (w > 0) {
            if (w % 2 == 1)ans = ans * cnt % z;
            cnt = cnt * cnt % z;
            w /= 2;
        }
        return ans;
    }

    friend bign powmod(const int &x, const bign &y, const bign &z) {
        bign ans = 1, cnt = x, w = y;
        while (w > 0) {
            if (w % 2 == 1)ans = ans * cnt % z;
            cnt = cnt * cnt % z;
            w /= 2;
        }
        return ans;
    }

    friend bign powmod(const bign &x, const int &y, const bign &z) {
        bign ans = 1, cnt = x;
        int w = y;
        while (w) {
            if (w & 1)ans = ans * cnt % z;
            cnt = cnt * cnt % z;
            w >>= 1;
        }
        return ans;
    }

    friend bign powmod(const bign &x, const bign &y, const int &z) {
        bign ans = 1, cnt = x, w = y;
        while (w > 0) {
            if (w % 2 == 1)ans = ans * cnt % z;
            cnt = cnt * cnt % z;
            w /= 2;
        }
        return ans;
    }

    friend bign powmod(const int &x, const bign &y, const int &z) {
        bign ans = 1, cnt = x, w = y;
        while (w > 0) {
            if (w % 2 == 1)ans = ans * cnt % z;
            cnt = cnt * cnt % z;
            w /= 2;
        }
        return ans;
    }

    friend bign powmod(const bign &x, const int &y, const int &z) {
        bign ans = 1, cnt = x;
        int w = y;
        while (w) {
            if (w & 1)ans = ans * cnt % z;
            cnt = cnt * cnt % z;
            w >>= 1;
        }
        return ans;
    }

    friend bign max(const bign &x, const bign &y) {
        return x > y ? x : y;
    }

    friend bign min(const bign &x, const bign &y) {
        return x < y ? x : y;
    }
};

int main() {
    bign a, b;
    return 0;
}

3. 二分查找

#include<bits/stdc++.h>
using namespace std;
int m,n;
    int a[100010];
//第一个大于x的数 
int find1(int x){
    int l=1,r=n;
    while(l<=r){
        int mid=(l+r)/2;
        if(a[mid]<=x) l=mid+1;
        else if(a[mid]>x) r=mid-1;
    }
    return l;
}
//第一个大于等于x得数 
int find2(int x){
    int l=1,r=n;
    while(l<=r){
        int mid=(l+r)/2;
        if(a[mid]<x) l=mid+1;
        else if(a[mid]>=x)r=mid-1;
    }
    return l;
}
//最后一个小于x的数 
int find3(int x){
    int l=1,r=n;
    while(l<=r){
        int mid=(l+r)/2;
        if(a[mid]<x) l=mid+1;
        else if(a[mid]>=x) r=mid-1;
    }

    return r;
}
//最后一个小于等于x得数 
int find4(int x){
    int l=1,r=n;
    while(l<=r){
        int mid=(l+r)/2;
        if(a[mid]<=x) l=mid+1;
        else if(a[mid]>x) r=mid-1;
    }
    return r;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i+=1) scanf("%d",&a[i]); //a数组升序 
    for(int shit=1;shit<=m;shit++){
        int x;
        scanf("%d",&x);
        int l=1,r=n;
        int mid;
        int a1=find1(x),a2=find2(x),a3=find3(x),a4=find4(x);
        if(a1<1||a1>n) printf("-1 "); else printf("%d ",a1);
        if(a2<1||a2>n) printf("-1 "); else printf("%d ",a2);
        if(a3<1||a3>n) printf("-1 "); else printf("%d ",a3);
        if(a4<1||a4>n) printf("-1 "); else printf("%d ",a4);
        if(a[1]>=x) printf("-1 ");  else printf("1 ");  //第一个小于x的数 直接看a1 XD 
        if(a[n]<=x) printf("-1 ");  else printf("%d ",n);//最后一个大于x的数 直接看an XD 
        puts(""); 
    }
    return 0;
}

4. 后缀表达式求值

#include <bits/stdc++.h>
using namespace std;
stack<double> sta;
char str[105];
int main()
{
    while (cin>>str) {
        if (str[0]=='+'||str[0]=='-'||str[0]=='*'||str[0]=='/') {
            double y=sta.top(); sta.pop();
            double x=sta.top(); sta.pop();
            switch(str[0]) {
                case '+': sta.push(x+y); break;
                case '-': sta.push(x-y); break;
                case '*': sta.push(x*y); break;
                case '/': sta.push(x/y); break;
                default: assert(false);
            }
        } else sta.push(atof(str));
    }
    cout<<setprecision(6)<<fixed<<sta.top()<<endl;
}

5. 01背包-体积

#include <bits/stdc++.h>
using namespace std;
const int MAXV=20010;
int n,v,vi,can[MAXV];
int main()
{
    cin>>n>>v;
    can[0]=true;
    for (int i=0;i<n;++i) {
        cin>>vi;
        for (int j=v;j>=vi;--j)
            if (can[j-vi])
                can[j]=1;
    }
    for (int j=v;j>=0;--j)
        if (can[j]) {
            cout<<v-j<<endl;
            break;
        }
    return 0;
}

6. 01背包-体积&价值

#include <bits/stdc++.h>
using namespace std;
const int MAXV=1010;
int n,v,ci,wi,opt[MAXV];
int main()
{
    cin>>v>>n;
    for (int i=0;i<n;++i) {
        cin>>ci>>wi;
        for (int j=v;j>=ci;--j)
            opt[j]=max(opt[j],opt[j-ci]+wi);
    }
    cout<<opt[v]<<endl;
    return 0;
}

7. 完全背包-体积&价值

#include <bits/stdc++.h>
using namespace std;
const int MAXV=1010;
int n,v,ci,wi,opt[MAXV];
int main()
{
    cin>>v>>n;
    for (int i=0;i<n;++i) {
        cin>>ci>>wi;
        for (int j=ci;j<=v;++j)
            opt[j]=max(opt[j],opt[j-ci]+wi);
    }
    cout<<opt[v]<<endl;
    return 0;
}

8. 多重背包-体积&价值

#include <bits/stdc++.h>
using namespace std;
int n,v,n2,c[110],w[110],opt[1010];
int main()
{
    scanf("%d%d",&v,&n);
    for (int i=0,mm,vv,tt;i<n;++i) {
        scanf("%d%d%d",&mm,&vv,&tt);
        for (int k=1;k<=mm;++k)
            for (int j=v;j>=vv;--j)
                opt[j]=max(opt[j],opt[j-vv]+tt);
    }
    cout<<opt[v]<<endl;
    return 0;
}

9. 二维背包

#include <bits/stdc++.h>
using namespace std;
const int MAXN=100+10;
int V,W,n,v[MAXN],w[MAXN],t[MAXN],ans,dp[1001][1001];
int main()
{
    cin>>V>>W>>n;
    for (int i=1;i<=n;++i) cin>>v[i]>>w[i]>>t[i];
    for (int i=1;i<=n;++i)
        for (int j=V;j>=v[i];--j)
            for (int k=W;k>=w[i];--k)
                dp[j][k]=max(dp[j][k],dp[j-v[i]][k-w[i]]+t[i]);
    for (int i=1;i<=V;++i)
        for (int j=1;j<=W;++j)
            ans=max(ans,dp[i][j]);
    cout<<ans<<endl;
}

10. 混合背包

#include<bits/stdc++.h>
using namespace std;
int n,v,v1[101],t1[101],m[101],dp[1001];
int main()
{
    scanf("%d%d",&v,&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",&m[i],&v1[i],&t1[i]);
    for(int i=1;i<=n;i++)
        if (m[i])
            for (int j=v1[i];j<=v;++j)
                dp[j]=max(dp[j],dp[j-v1[i]]+t1[i]);
        else
            for (int j=v;j>=v1[i];--j)
                dp[j]=max(dp[j],dp[j-v1[i]]+t1[i]);
    printf("%d\n",dp[v]);
    return 0;
}

11. 分组背包

#include <bits/stdc++.h>
using namespace std;
const int MAXV=1010;
const int MAXN=101;
int n,v,k,ki[MAXN],vi[MAXN][MAXN],ti[MAXN][MAXN],opt[MAXV];
int main()
{
    cin>>v>>k;
    for (int i=1;i<=k;++i) {
        cin>>ki[i];
        for (int j=1;j<=ki[i];++j)
            cin>>vi[i][j]>>ti[i][j];
    }
    for (int i=1;i<=k;++i)
        for (int j=v;j>=0;--j)
            for (int x=1;x<=ki[i];++x)
                if (j>=vi[i][x])
                    opt[j]=max(opt[j],opt[j-vi[i][x]]+ti[i][x]);
    cout<<opt[v]<<endl;
    return 0;
}

12. 区间dp

#include<bits/stdc++.h>
using namespace std;
int main(){
    int dp[400][400],sum[400]={0},value[400];
    memset(dp,-0xcfffff,sizeof(dp));
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>value[i];
        dp[i][i]=0;
    }
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+value[i];
    }
    for(int L=2;L<=n;L++){
        for(int i=1,j=i+L-1;j<=n;i++,j++){
            for(int k=i;k<j;k++){
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
            }
        }
    }
    cout<<dp[1][n];
    return 0;
}

13. 区间dp-环

#include<bits/stdc++.h>
using namespace std;
int dp[2*400][2*400],sum[2*400]={0},value[2*400];
int main(){
    memset(dp,0x3f,sizeof(dp));
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>value[i];
        value[i+n]=value[i];
    }
    for(int i=1;i<=n*2;i++){
        sum[i]=sum[i-1]+value[i];
        dp[i][i]=0;
    }
    for(int L=2;L<=n;L++){
        for(int i=1,j=i+L-1;j<=2*n;i++,j++){
            for(int k=i;k<j;k++){
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
            }
        }
    }
    int maxn=0xc3f3f3f;
    for(int i=1;i<=n;i++){
        if(maxn>dp[i][n+i-1]) maxn=dp[i][n+i-1];
    }
    cout<<maxn;
    return 0;
}

14. 最大连续段和

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int a[n+10];
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int num=0;
    int ans=0;
    for(int i=1;i<=n;i++){
        num+=a[i];
        ans=max(ans,num);
        if(num<0) num=0;
    }
    cout<<ans;
    return 0;
}

15. 最长公共子序列

#include<bits/stdc++.h>
using namespace std;

const int MAX=1010;
int l1,l2,s1[MAX],s2[MAX],dp[MAX][MAX];

int LCS(int i,int j)
{
    if (i==0||j==0) return 0;
    if (dp[i][j]>=0) return dp[i][j];
    if (s1[i]==s2[j]) {
        return dp[i][j]=LCS(i-1,j-1)+1;
    } else {
        return dp[i][j]=max(LCS(i-1,j),LCS(i,j-1));
    }
}
int main()
{
    cin>>l1>>l2;
    for (int i=1;i<=l1;++i) cin>>s1[i];
    for (int i=1;i<=l2;++i) cin>>s2[i];
    memset(dp,-1,sizeof(dp));
    cout<<LCS(l1,l2)<<endl;
    return 0;
}

16. 最长公共子串

#include<bits/stdc++.h>
using namespace std;
int n,m,f[1020][1020];
string a,b;
int main(){
    cin>>a>>b;
     n=a.size();
     m=b.size();
     if(n<m){
        swap(n,m); swap(a,b);
     }
     if(a[0]==b[0]) f[0][0]=1;
    for(int i=1;i<n;i++){
        for(int j=0;j<m;j++){
            if(a[i]==b[j]) f[i][j]=f[i-1][j-1]+1;
            if(a[i]!=b[j]) f[i][j]=0;
        }
    }
    int ans=-1;
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(ans<f[i][j]) ans=f[i][j];
    cout<<ans;

    return 0;
}

17. 最长上升子序列

#include <iostream>
using namespace std;
const int MAX = 100010;
int n,a[MAX],f[MAX],len;
int main()
{
    cin>>n;
    for (int i=0;i<n;++i) cin>>a[i];
    len=1;
    f[0]=a[0];
    for (int i=1;i<n;++i) {
        int pos=lower_bound(f,f+len,a[i])-f;
        f[pos]=a[i];
        len=max(len,pos+1);
    }
    cout<<len<<endl;
}

18. Dijistra

#include<bits/stdc++.h> 
using namespace std;
const int n=10001000,m=100001000;
unsigned long long head[n],ver[n],edge[m],next[m],d[n];
bool visit[n];
unsigned long long nn,mm,tot;
unsigned long long s;
priority_queue<pair<unsigned long long,unsigned long long> > q;
void add(unsigned long long x,unsigned long long y,unsigned long long  z){
    ver[++tot]=y,edge[tot]=z,next[tot]=head[x],head[x]=tot;
}

void dijistra(){
    memset(d,0x3f,sizeof(d));
    memset(visit,0,sizeof(visit));
    d[s]=0;
    q.push(make_pair(0,s));
    while(q.size()){
        unsigned long long x=q.top().second; q.pop();
        if(visit[x]) continue;
        for(unsigned long long i=head[x];i;i=next[i]){
            unsigned long long y=ver[i];
            unsigned long long z=edge[i];
            if(d[y]>d[x]+z){
                d[y]=d[x]+z;
                q.push(make_pair(-d[y],y));
            }
        }
    } 
}
int main(){
    cin>>nn>>mm>>s;
    for(unsigned long long i=1;i<=mm;i++){
        unsigned long long x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
    }
    dijistra();
    for(unsigned long long i=1;i<=nn;i++) cout<<d[i]<<" ";
    return 0; 
}

19. Floyd-负环

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3F3F3F3F;
int n,m,g[1010][1010],s,t,ans;
int main()
{
    memset(g,INF,sizeof(g));
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=c;
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if (g[i][k]<INF&&g[k][j]<INF)             
                    g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
    cin>>s>>t;
    ans=g[s][t];
    if (ans==INF) ans=-1;
    for (int i=1;i<=n;++i)
        if (g[i][i]<0&&g[s][i]<INF&&g[i][t]<INF)
            ans=-1;
    cout<<ans<<endl;
    return 0;
}

20. SPFA-负环

#include <bits/stdc++.h>
using namespace std;
const int MAXN=10010;
const int MAXE=100010;
const int INF=0x3f3f3f3f;
struct Edge { int u,v,w; } e[MAXE];
int n,m,s,t,d[MAXN];
int main()
{
    scanf("%d%d",&n,&m);
    memset(d,INF,sizeof(d));
    for (int i=0;i<m;++i)
        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
    scanf("%d%d",&s,&t);
    d[s]=0;
    int tt;
    for (tt=0;tt<n;++tt) {
        bool f=true;
        for (int i=0;i<m;++i)
            if (d[e[i].u]<INF&&d[e[i].u]+e[i].w<d[e[i].v]) {
                d[e[i].v]=d[e[i].u]+e[i].w;
                f=false;
            }
        if (f) break;
    }
    if (tt==n||d[t]==INF) cout<<-1<<endl;
    else cout<<d[t]<<endl;
    return 0;
}

21.线段树—单点修改，区间球最小值

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
const int INF=0x7f7f7f7f;
int n,val[MAXN<<2],init_val[MAXN];
int m;
void push_up(int rt){
    val[rt]=min(val[rt*2],val[rt*2+1]);
}
void build(int rt,int l,int r){
    if(l==r){
        val[rt]=init_val[i];
    }
    else{
        int mid=(l+r)/2;
        build(rt*2,l,mid);
        build(rt*2+1,mid+1,r);
        push_up(rt); 
    }
}
void update_one(int rt,int l,int r,int idx,int add){ //单点修改，给init_val[idx]加上add 
    if(l==r){
        val[rt]+=add;
        return;
    }
    int mid=(l+r)/2;
    if(idx<=mid){
        update_one(rt*2,l,mid,idx,add);
    }
    else update_one(rt*2+1,mid+1,r,idx,add);
    push_up(rt);

} 
int query(int rt,int l,int r,int ql,int qr){ //一共三种情况 
    if(ql>r||qr<l){ //求最小值的区间和现在这个区间没有关系 
        return INF;
    }
    if(ql<=l&&qr>=r) return val[rt]; //这个区间被完整包含在球最小值的区间里 
    push_down(rt);
    int mid=(l+r)/2;
    return min(query(rt*2,l,mid,ql,qr),query(rt*2+1,mid+1,r,ql,qr));
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>init_val[i];
    build(1,1,n);   //建树 
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        cout<<query(1,1,n,a,b)<<endl;
    } 
    return 0;
}