graph TD
A[问题] -->B[确定性问题]
A --> C[最优化问题]
B --> D[模拟]
C -->E[有限集]
C -->F[无限集]
C -->K[最值问题]

E -->G[DP]
E -->H[贪心]
E -->I[DFS]
K -->J[二分]
F -->J[二分]

素数

ifPrime(int num){
    if(num<=1)return false;
    for(int i = 2; i*i<=num; i++){
        if(num%i==0)return false;
    }
    return true;
}

for(int i = 2; i<=n; i++){
    if(isPrime[i]){
        for(int j = i*2; j<=num; j+=i){
            isPrime[j] = false;
        }
    }
}

公因数公倍数

//公因数计算最大公因数的常用方法之一是欧几里得算法（辗转相除法），这个算法的原理是：

//设a和b是两个正整数，且a > b，若a能被b整除，则b是a和b的最大公因数；
//否则，设c是a除以b的余数，即c = a % b，那么b和c的最大公因数就是a和b的最大公因数。
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}
//最小公倍数
int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

二分

// 找满足某个条件的第一个数  即右半段
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;  
        else l = mid + 1;
    }
    return l;
}

// 找满足某个条件的最后一个数  即左半段
int find(vector<int> g, int target){
        int l = 0;
        int r = g.size();
        while(l<r){
            int mid = l+r+1>>1;
            if(mid>=g.size())break;
            if(g[mid]<=target)l = mid;
            else r = mid-1;
        }
        return l;
    }

插入排序，平均O(n^2),最好O(n)，最坏O(n^2),空间复杂度O(1);

for(int i = 1; i<=n; i++){
    int x = a[i];
    int j = i-1;
    //找到a[i]应该在的位置，进行交换
    while(j>=0 && x<a[j]){
        a[j+1] = a[j];
        j--;
    }
    a[j+1] = x;//应该在的位置
}

约数个数

一个数的约数是由这个数的几个质因子相乘得到的。

例如：12 的质因子有 2，3。12的约数有：1，2，3，4，6，12。

约数1 是由 0 个 2， 0 个3相乘得到的。
约数2 是由 1 个 2， 0 个3相乘得到的。
约数3 是由 0 个 2， 1 个3相乘得到的。
约数4 是由 2 个 2， 0 个3相乘得到的。
约数6 是由 1 个 2， 1 个3相乘得到的。
约数12 是由 2 个 2， 1 个3相乘得到的。
12 可以分解为：2^2*3^1。所以2可以取 0 ~ 2个，3种取法。3可以取 0~1 个，2种取法。12的约数一共：2 * 3 = 6个。

也就是：把一个数N 写成：N = (p1^x1^)(p^x2)(p3^x3)…(pk^xk)，其中pi为质数。则N的约数个数为：(x1+1)(x2+1)(x3+1)…(xk+1)

int main()
{
    int T; 
    cin >> T;
    unordered_map<int, int> h;
    while(T--)
    {
        int n; cin >> n;
        //依次求出质数
        for(int i = 2; i <= n / i; i++)
        {
            while(n % i == 0)
            {
                //指数+1
                h[i] ++;
                n = n / i;
            }
        }
        //如果有剩余，也是一个质因子
        if(n > 1) h[n]++;
    }

    long long  res = 1;
    for(auto iter = h.begin(); iter != h.end(); iter++)
    {
        //res = (x1+1)(x2+1)(x3+1)…(xk+1)
        res = res * (iter->second + 1) % mod ;
    }
    cout << res;
}

字符串哈希

int p[N], h[N];
int P = 13331;//13331
typedef unsigned long long ULL;
ULL query(int l, int r){
    return h[r] - h[l-1]*p[r-l+1];
}
char str[N];
int main(){
    int n, m;
    cin>>n>>m>>str+1;


    p[0] = 1;
    for(int i = 1; i<=n; i++){
        p[i] = p[i-1]*P;
        h[i] = h[i-1]*P+str[i];
    }
    while(m--){
        int l1, r1, l2, r2;
        cin>>l1>>r1>>l2>>r2;
        if(query(l1, r1) == query(l2, r2)){
            cout<<"Yes"<<endl;
        }else{
            cout<<"No"<<endl;
        }
    }

}

堆排序

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int heap[N],heapSize;
int n, m;

void down(int u){
    int t =u;//t存储最小值,根叶子三个中最小值，所以下面代码不能是heap[u*2+1]<heap[u]
    if(u*2<=heapSize && heap[u*2]<heap[t]){
        t = 2*u;
    }
    if(u*2+1<=heapSize && heap[u*2+1]<heap[t]){
        t = 2*u+1;
    }
    if(u!=t){
         swap(heap[u], heap[t]);
         down(t);
    }

}
int main(){
    cin>>n>>m;
    heapSize = n;
    for(int i =1; i<=n; i++){
        cin>>heap[i];
    }
    for(int i =n/2; i; i--){
        down(i);
    }

    for(int i = 1; i<=m; i++){
        cout<<heap[1]<<" ";
        heap[1] = heap[heapSize--];
        down(1);
    }
}

快速排序

void quick_sort(int q[], int l, int r)
{
    //递归的终止情况
    if(l >= r) return;

    //第一步：分成子问题
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while(i < j)
    {
        do i++; while(q[i] < x);
        do j--; while(q[j] > x);
        if(i < j) swap(q[i], q[j]);
    }

    //第二步：递归处理子问题
    quick_sort(q, l, j), quick_sort(q, j + 1, r);

    //第三步：子问题合并.快排这一步不需要操作，但归并排序的核心在这一步骤
}

归并排序

void merge_sort(int q[], int l, int r)
{
    //递归的终止情况
    if(l >= r) return;
    //第一步：分成子问题
    int mid = l + r >> 1;
    //第二步：递归处理子问题
    merge_sort(q, l, mid ), merge_sort(q, mid + 1, r);
    //第三步：合并子问题
    int k = 0, i = l, j = mid + 1, tmp[r - l + 1];
    while(i <= mid && j <= r)
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    while(i <= mid) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];
    for(k = 0, i = l; i <= r; k++, i++) q[i] = tmp[k];
}

DFS

void dfs(int u){
    //到达底部
    if(u>n){
        for(int i=1; i<=n; i++){
            System.out.print(path[i]+" ");
        }
        System.out.println();
    } 

    for(int i = 1; i<=n; i++){
        if(!state[i]){//没用过
            state[i] = true;
            path[u] = i;
            dfs(u+1);
            state[i] = false;
        }
    }
    }

BFS

class Pair{
}

哈希函数

-（1）开放寻址法

//开放寻址法
int find(int k){
    //保证是正数
    int t = (k%N+N)%N;
    while(h[t]!=INF && h[t]!=k){//当前位置被占了，找相邻的
        t++;
        if(t == N) t = 0;
    }
    return t;
}

-（2）拉链法

void insert(int v){
   int x = (v%N+N)%N;
   e[idx] = v;
   ne[idx] = h[x];
   h[x] = idx++;
}
bool find(int val){
   int x = (val%N+N)%N;
   for(int i = h[x]; i!=INF; i = ne[i]){
       if(e[i] == val){
           return true;
       }
   }
   return false;
}

KMP

关于KMP算法中算法中next数组的理解，我们知道next数组的含义是前缀和后缀相同的最大长度，部分匹配值即假如next[i] = j,含义即子串P P[1,j] = P[i-j+1, j]（下标从1开始），那么匹配时若S[i]!=P[j+1]时（为什么是j+1，因为从j+1开始不匹配，那么j以及之前的匹配，需要跳转j=ne[j])，j = ne[j]意思就是从头开始P[1, ne[j]]已经不需要匹配了，下一次只需要匹配ne[j]+1（因为S和P一旦不匹配我们暴力做法就是P从头开始，但是KMP优化就是找到了最长前缀，不需要从头开始）

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}

Trie

void insert(char *str){
    int p = 0;
    for(int i = 0; str[i]; i++){
        int u = -1;
        if(str[i] == 'R') 
            u = 0;
        else{
            u = 1;
        }
        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
    cnt[p]++;

}
int query(char *str)
{
    int p = 0;
    for(int i = 0; str[i]; i++)
    {
        int u = str[i] - 'a';
        if(!son[p][u]) return 0;  //该节点不存在，即该字符串不存在
        p = son[p][u]; 
    }
    return cnt[p];  //返回字符串出现的次数
}

区间合并

区间合并

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
typedef pair<int, int> PII;
vector<PII> v, res;
int n;
bool cmp(PII a, PII b){
    return a.first<b.first;
}
int main(){
    cin>>n;
    while(n--){
        int l, r;
        cin>>l>>r;
        v.push_back({l,r});
    }
    sort(v.begin(), v.end(), cmp);

    int st = -2e9, ed = -2e9;
    for(auto t:v){
        if(ed<t.first){
            if(ed!=-2e9) res.push_back({st, ed});
            st = t.first, ed = t.second;
        }
        else if(ed<t.second){
            ed = t.second;
        }
    }

    res.push_back({st, ed});
    cout<<res.size();
}

离散化

区间和

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

using namespace std;
const int N = 300010, INF = 0x3f3f3f3f;
typedef pair<int, int> PII;
vector<PII> v;
vector<PII> q;
int a[N], s[N];

vector<int> alls;
int find(int v){
    int l =0, r = alls.size();
    while(l<r){
        int mid = l+r>>1;
        if(alls[mid]>=v)r = mid;
        else l= mid+1;
    }
    return l+1;
}
int main(){
    int n, m;
    cin>>n>>m;
    for(int i = 0; i<n; i++){
        int x, c;
        cin>>x>>c;
        v.push_back({x, c});
        alls.push_back(x);//将所有用到的索引加进来
    }
    while(m--){
        int l, r;
        cin>>l>>r;
        q.push_back({l, r});
        alls.push_back(l);
        alls.push_back(r);
    }
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()),alls.end());//移除重复的索引
    for(auto add:v){

        a[find(add.first)]+=add.second;

    }
     for (int i = 1; i <= alls.size(); i++) s[i] = s[i-1] + a[i];
    //处理后m次询问操作
    for (auto item : q) {
        int l = find(item.first);
        int r = find(item.second);
        printf("%d\n", s[r] - s[l-1]);
    }


}

滑动窗口

//思路就是比如 1 3 5 4，查找最大的元素时，我们看 5 加入时，前面的 3 永远不可能是最大元素了，所以思路就是加一个元素，然后再双端队列中循环删除比他小的（找最大值的情况，另外为什么不删除<=新加入的后面代码中有说到）
#include<iostream>
#include<deque>
using namespace std;
const int N = 1000010;
int a[N];
int n, k;
int main(){
    cin>>n>>k;
    for(int i = 1; i<=n; i++){
        cin>>a[i];

    }
    deque<int> q;
    for(int i = 1; i<=n; i++){
        //新元素进来，重复的元素要么全被干掉，要么全被保留。考虑是否有漏弹、误弹现象只需要考虑重复元素被保留的情况。到了弹出的时刻，因为队列中元素由老到少排队，队头是资历最老的（最先进来的）。于是重复元素会被按序弹出。
        while(q.size() && q.back()>a[i]) q.pop_back();

        q.push_back(a[i]);
        if(i - k >= 1 && q.front() == a[i - k])//若队头是否滑出了窗口，队头出队 
            q.pop_front();
        if(i-k>=0){
            cout<<q.front()<<" ";
        }
    }
    cout<<endl;q.clear();
    for(int i = 1; i<=n; i++){

        while(q.size() && q.back()<a[i]) q.pop_back();

        q.push_back(a[i]);
        if(i - k >= 1 && q.front() == a[i - k])//若队头是否滑出了窗口，队头出队 
            q.pop_front();
        if(i-k>=0){
            cout<<q.front()<<" ";
        }
    }

}

并查集

另外路径压缩，当一棵树找他的父结点时，途径的所有节点直接指向父结点如 root->node1->node2(从 node2找父结点的同时进行路径优化root->node1、root->node2)

void init(int n){//初始化根节点
    for(int i = 1; i<=n; i++) p[i] = i;
}
int find(int x){
    //if(p[x]!=x) x = find(p[x]);//不进行路径压缩
    if(p[x]!=x) p[x] = find(p[x]);//同时进行路径压缩
    return p[x];
}
void merge(int x, int y){//合并集合
    p[find(x)] = find(y);
}
int main(){
    int n, m;
    cin>>n>>m;
    init(n);
    while(m--){
        char ch;
        int x, y;
        cin>>ch>>x>>y;
        if(ch == 'M')merge(x, y);
        else{
            if(find(x) == find(y))cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }

}

prim

int dist[n],state[n],pre[n];
dist[1] = 0;
for(i : 1 ~ n)
{
    t <- 没有连通起来，但是距离连通部分最近的点;
    state[t] = 1;
    更新 dist 和 pre;
}

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

const int N = 510;
int g[N][N];//存储图
int dt[N];//存储各个节点到生成树的距离
int st[N];//节点是否被加入到生成树中
int pre[N];//节点的前去节点
int n, m;//n 个节点，m 条边

void prim(){
    memset(dt,0x3f, sizeof(dt));//初始化距离数组为一个很大的数（10亿左右）
    int res= 0;
    dt[1] = 0;//从 1 号节点开始生成 

    for(int i = 0; i<n; i++){
        int t = -1;
        for(int j = 1; j<=n; j++){
            if(!st[j] && (t==-1 || dt[j]<dt[t])){
                t = j;
            }
        }
        if(dt[t] == 0x3f3f3f3f) {
            cout << "impossible";
            return;
        }
        st[t] = 1;// 选择该点
        res += dt[t];
        for(int i = 1; i <= n; i++)//更新生成树外的点到生成树的距离
        {
            if(dt[i] > g[t][i] && !st[i])//从 t 到节点 i 的距离小于原来距离，则更新。
            {
                dt[i] = g[t][i];//更新距离
                pre[i] = t;//从 t 到 i 的距离更短，i 的前驱变为 t.
            }
        }
    }
    cout << res;
}

void getPath()//输出各个边
{
    for(int i = n; i > 1; i--)//n 个节点，所以有 n-1 条边。

    {
        cout << i <<" " << pre[i] << " "<< endl;// i 是节点编号，pre[i] 是 i 节点的前驱节点。他们构成一条边。
    }
}

int main()
{
    memset(g, 0x3f, sizeof(g));//各个点之间的距离初始化成很大的数
    cin >> n >> m;//输入节点数和边数
    while(m --)
    {
        int a, b, w;
        cin >> a >> b >> w;//输出边的两个顶点和权重
        g[a][b] = g[b][a] = min(g[a][b],w);//存储权重
    }

    prim();//求最下生成树
    //getPath();//输出路径
    return 0;
}

前缀和与差分

#include<iostream>
using namespace std;
const int N = 1010;
int a[N][N];
int s[N][N];
int main(){
    int n,m, q;
    cin>>n>>m>>q;
    for(int i = 1; i<=n; i++){
        for(int j = 1; j<=m; j++){
            cin>>a[i][j];
            //前缀和
            s[i][j] = s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
        }
    }

    while(q--){
        int x1, y1,x2, y2;
        cin>>x1>>y1>>x2>>y2;
        //区间和
        cout<<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<<endl;
    }
}

#include<iostream>
using namespace std;
const int N = 1010;
int b[N][N];
int a[N][N];
void insert(int x1, int y1, int x2, int y2, int c){//维护差分矩阵
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}
int main(){
    int n,m, q;
    cin>>n>>m>>q;
    for(int i = 1; i<=n; i++){
        for(int j = 1; j<=m; j++){
            int c;cin>>c;
            insert(i, j, i, j, c);
        }
    }
    while(q--){
        int x1, y1, x2, y2,c;
        cin>>x1>>y1>>x2>>y2>>c;
        insert(x1, y1, x2, y2, c);
    }
    for(int i = 1; i<=n; i++){
        for(int j = 1; j<=m; j++){
            a[i][j] = a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];//前缀和

        }
    }
    for(int i = 1; i<=n; i++){
        for(int j = 1; j<=m; j++){
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
}

多路归并

序列

每次找第一列的最小值，找到后就是第一个值的最小值，然后 对应行位置需要+1到下一个列

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>

using namespace std;
const int N  = 2010;
int a[N], b[N], c[N], n, m;

typedef pair<int, int> PII;
void merge(){
    priority_queue<PII, vector<PII>, greater<PII>> q;

   for(int i = 0; i<n; i++){
       q.push({a[0]+b[i], 0});

   }
   for(int i = 0; i<n; i++){
       auto t = q.top();
       q.pop();
       c[i] = t.first;
       int second = t.second;
       q.push({c[i]-a[second]+a[second+1], second+1});
   }
   memcpy(a, c, sizeof a);


}
int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &m, &n);
        for(int i = 0; i<n; i++){
            scanf("%d", &a[i]);
        }
        sort(a, a+n);
        for(int i = 0; i<m-1; i++){
            for(int j = 0; j<n; j++){
                scanf("%d", &b[j]);
            }
            merge();
        }

        for(int i = 0; i<n; i++){
            printf("%d ", a[i]);
        }
        puts("");
    }
}

树形 DFS

void add(int a, int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
void dfs(int u){
    st[u] = true;
    for(int i = h[u]; i!=-1; i = ne[i]){
        int j = e[i];
        if(!st[j])
            dfs(j);

    }
}

树的重心

#include<iostream>
#include<cstring>
using namespace std;
const int N = 100010;
const int M = 2*N+10;
int e[M],ne[M],h[N], idx;
int ans = N;
int n;
bool st[N];
void add(int a, int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
int dfs(int u){
    int sum = 1;//以该点为root总链接的节点数目
    int res = 0;
    st[u] = true;
    for(int i = h[u]; i!=-1; i = ne[i]){
        int j = e[i];
        if(!st[j]){
            int s = dfs(j);
            res = max(res, s);//连通块最大值
            sum+=s;//更新sum
        }

    }
    res = max(res, n - sum); // 选择u节点为重心，最大的 连通子图节点数(即将这个树分成两个，一个是该节点联通的，另一个是该节点不联通的一部分)
    ans = min(res, ans); //遍历过的假设重心中，最小的最大联通子图的 节点数
    return sum;
}
int main(){
memset(h, -1, sizeof h); //初始化h数组 -1表示尾节点
    cin>>n;
    for(int i = 0; i<n-1; i++){
        int a,b;
        cin>>a>>b;
        add(a, b);
        add(b,a);//无向
    }
    dfs(1);
    cout<<ans<<endl;

    return 0;
}

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 510,M = 100010;
int h[N],w[M],e[M],ne[M];
bool st[N];
int idx,n,m;
int dist[N];
void add(int a, int b, int c){
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}
void dijkstra(){
    dist[1] = 0;
    for(int i = 0;i<n;i++){
        int t = -1;
        for(int j = 1;j<=n;j++){
            if(!st[j] && (t == -1 || dist[j]<dist[t])){
                t = j;
            }

        }
        st[t] = true;
        for(int i = h[t]; i!=-1; i = ne[i]){
            int j = e[i];
            dist[j] = min(dist[j], dist[t]+w[i]);
        }
    }
}
int main(){
    cin>>n>>m;
    memset(dist, 0x3f, sizeof dist);
    memset(h, -1, sizeof h);
    while(m--){
        int a, b, c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    dijkstra();

    if (dist[n] != 0x3f3f3f3f)//如果dist[n]被更新了，则存在路径
        cout << dist[n];
    else
        cout << "-1";

}

import java.util.*;
import java.io.*;

class Main{
    static final int N = 510;
    static final int M = 100005;
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] w = new int[M];
    static int[] ne = new int[M];
    static int n, m,idx;
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
    static class Pair{
        int first;
        int second;
        Pair(int x, int y){
            first = x;
            second = y;
        }
    }
    static void add(int a, int b, int c){
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    static void dijkstra(){
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[1] = 0;

        PriorityQueue<Pair> queue = new PriorityQueue<Pair>((a, b) -> Integer.compare(a.second, b.second));
        queue.offer(new Pair(1, 0));

        while (!queue.isEmpty()) {
            Pair pair = queue.poll();
            int node = pair.first;
            int dis = pair.second;
            if (st[node]) {
                // 不再需要 continue，确保所有可达节点都被处理
                continue;
            }
            st[node] = true;
            for (int i = h[node]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] > dist[node] + w[i]) {
                    dist[j] = dist[node] + w[i];
                    queue.offer(new Pair(j, dist[j]));
                }
            }
        }

    }
    public static void main(String[] args) throws IOException{
        Arrays.fill(h, -1);
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer tokenizer = new StringTokenizer(read.readLine());
        n = Integer.parseInt(tokenizer.nextToken());
        m = Integer.parseInt(tokenizer.nextToken());

        for(int i = 0; i<m; i++){
            int a, b, c;
            tokenizer = new StringTokenizer(read.readLine());
            a = Integer.parseInt(tokenizer.nextToken());
            b = Integer.parseInt(tokenizer.nextToken());
            c = Integer.parseInt(tokenizer.nextToken());
            add(a, b, c);
        }
        dijkstra();
        if(dist[n] == Integer.MAX_VALUE){
            writer.write(String.valueOf(-1));
        }else{
            writer.write(String.valueOf(dist[n]));
        }

        read.close();
        writer.close();

    }

}

邻接矩阵，适用于稠密图

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 510, M = 100010;

int g[N][N], dist[N];

bool st[N];
int n, m;
int dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for(int i = 0; i<n; i++){
        int t = -1;
        for(int j = 1; j<=n; j++){
            if(!st[j] && (t==-1 || dist[j]<dist[t])){
                t = j;
            }
        }
        st[t] = true;
        for(int j = 1;j<=n; j++){
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}
int main(){
    cin>>n>>m;
    memset(g, 0x3f, sizeof g);
    while(m--){
        int a, b, c;
        cin>>a>>b>>c;
        g[a][b] = min(g[a][b], c);

    }

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

spfa

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N = 100010;
int e[N],w[N], ne[N], h[N];
int dist[N];
int idx, n, m;
bool st[N];

void add(int a, int b, int c){
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}
int spfa(){
    queue<int> q;
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    q.push(1);
    st[1] = true;
    while(q.size()){
        auto t = q.front();
        q.pop();
        st[t] = false;
        for(int i = h[t]; i!=-1; i = ne[i]){
            int j = e[i];
            if( dist[t]+w[i] < dist[j]){
                dist[j] = dist[t]+w[i];

                if(!st[j]){
                    q.push(j);
                    st[j] = true;
                }
            }

        }

    }

    return dist[n];

}
int main(){
    memset(h, -1, sizeof h);
    cin>>n>>m;
    while(m--){
        int a, b, c;
        cin>>a>>b>>c;
        add(a, b, c);
    }
    int t = spfa();
    if (t == 0x3f3f3f3f) puts("impossible");
    else printf("%d\n", t);

}

超级原点的单源最短路径

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>//堆的头文件

using namespace std;

typedef pair<int, int> PII;//堆里存储距离和节点编号


const int N = 300010;
int n, m, k, q;
int e[N], w[N], h[N],ne[N], dist[N];
bool st[N];
int idx;
void add(int a, int b, int c){
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}


void dijkstra(){
    priority_queue<PII, vector<PII>, greater<PII>> q;
    dist[0]=0;      //超级源点的下标为0，从超级源点开始做单源最短路**

    q.push({0,0});
    while(q.size()){
        auto t = q.top();
       q.pop();
        int distance = t.first;
        int ver = t.second;
         if(st[ver]) continue;
        st[ver] = true;
        for(int i = h[ver]; i!=-1; i = ne[i]){
            int j = e[i];
            if(dist[j]>dist[ver]+w[i]){
                dist[j] = dist[ver]+w[i];
                q.push({dist[j], j});
            }
        }
    }

}

int main(){
    memset(h, -1, sizeof h);
    memset(dist, 0x3f, sizeof dist);

    cin>>n>>m;
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    cin>>k;
    while(k--){//超级原点
        int val;
        cin>>val;
        add(0, val , 0);


    }
    dijkstra();
    cin>>q;
    while(q--){
        int val; cin>>val;
        cout<<dist[val]<<endl;
    }


}

多源最短路径

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

using namespace std;

const int N = 210, INF = 0x3f3f3f3f;

int n, m, k;
int g[N][N];

int main()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= n; j ++ )
            if(i == j) g[i][j] = 0;
            else g[i][j] = INF;

    for(int i = 0; i < m; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = min(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 ++ )
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);

    while(k -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if(g[a][b] > INF / 2) puts("impossible");
        else cout << g[a][b] << endl;
    }

    return 0;
}