九阳神功

基础算法

// 一、基础算法————————————快排
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]);
    }
    //j,j+1做边界则x不能取v[r]; i-1,i做边界则x不能取v[l]
    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;
    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 (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}


// 三、基础算法————————————二分查找
// 整数二分模板(两种)
// 返回的l是第一个满足check条件的下标
int bsearch_1(int l, int r){
    while (l < r){
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l; 
}

// 返回的l是最后一个满足check条件的下标
int bsearch_2(int l, int r){
    while (l < r){
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l; 
}

// 浮点数二分模板
double bsearch_3(double l, double r){
    const double eps = 1e-6;   // eps 表示精度,取决于题目对精度的要求
    while (r - l > eps){
        double mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}


// 四、基础算法————————————高精度
// 高精度加法(A,B都在1e6的量级)    C = A + B, A >= 0, B >= 0 
vector<int> add(vector<int> &A, vector<int> &B){ // 156348 A[0]=8,A[1]=4方便进位
    if (A.size() < B.size()) return add(B, A);
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ ){
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    return C;
}

// 高精度减法(A,B都在1e6的量级)    C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B){
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ ){
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

// 高精度*低精度(A在1e6的量级, b在1e4的量级)    C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int b){
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ ){ 
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

// 高精度/低精度(A在1e6的量级, b在1e4的量级)    A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r){
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i -- ){
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}


// 五、基础算法————————————前缀和
// 一维前缀和 s[i] = v[0]+v[1]+...+v[i-1]
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i]; // 前缀和的初始化

// 二维前缀和
// s[i][j]第i行j列格子(包括i,j)左上部分所有元素的和
#include <iostream>
using namespace std;

const int N = 1010;
int n, m, q;
int s[N][N];

int main(){
    scanf("%d%d%d", &n, &m, &q);

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &s[i][j]);

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

    while (q -- ){
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
    }
    return 0;
}


// 六、基础算法————————————差分
/* 
原数组  6,4,3,2,7   差分数组  6,-2,-1,-1,5
若对a[0],a[1],a[2]...a[n-1];存在b[0],b[1],b[2]...b[n-1];使得a[i]=b[0]+b[1]+...+b[i]. 则b是a的差分, a是b的前缀和
若想对a[i](l <= i <= r) + c,我们可以令b[l] + c, b[r+1] - c; 可以把O(n)的操作简化为O(1)的操作
*/
void insert(int l, int r, int c){
    b[l] += c;
    b[r + 1] -= c;
}
for (int i = 1; i <= n; i ++ ) insert(i, i, a[i]); // 构造差分数组b

// 二维差分
#include<iostream>
using namespace std;

const int N = 1e3 + 10;
int a[N][N], b[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 ++)
            scanf("%d", &a[i][j]);
            
    for(int i = 1; i<= n; i ++)
        for(int j = 1; j <= m; j ++)
            insert(i, j, i, j, a[i][j]);
            
    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 ++){
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
            cout << b[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}


// 七、基础算法————————————滑动窗口
int lengthOfLongestSubstring(string s) {
    int n = s.size();
    map<char, int> mp;
    int res = 0;
    for(int l = 0, r = 0; r < n; r ++){
        mp[s[r]] ++;
        while(l < n && mp[s[r]] > 1) mp[s[l ++]] --;
        res = max(res ,r - l + 1);
    }
    return res;
}


// 八、基础算法————————————位运算
n >> 1 //会把最低位去掉    
n & 1  //n为奇数时,n&1的结果就是1,二进制n的最低位为1  n为偶数时,n&1的结果就是0,二进制n的最低位为0
n & (n - 1) // 自动把最低位的1去掉
n & -n // 返回n的最后一位1   比如 n = 100100 = 36, 则 n & -n = 100 = 4


// 九、基础算法————————————离散化
/*
假定有一个无限长的数轴,数轴上每个坐标上的数都是 0 现在,我们首先进行 n 次操作,每次操作将某一位置 x 上的数加 c
接下来,进行 m次询问,每个询问包含两个整数 l 和 r, 你需要求出在区间 [l,r]之间的所有数的和. 
−1e9 ≤ x ≤ 1e9, 1 ≤ n,m ≤ 1e5, −1e9 ≤ l ≤ r ≤ 1e9
*/
vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素
// 二分求出x对应的离散化的值
int find(int x){ // 找到第一个大于等于x的位置
    int l = 0, r = alls.size() - 1;
    while (l < r){
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l + 1; xx// 映射到 1, 2, ...n (从1开始是因为要求前缀和)
}


// 离散化题目
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
const int N = 300010;
int n, m;
int a[N], s[N];
vector<int> alls;//存入下标容器
vector<pair<int, int>> add, query;//add增加容器,存入对应下标和增加的值的大小  //query存入需要计算下标区间和的容器

int find(int x){
    int l = 0, r = alls.size() - 1;
    while (l < r){//查找大于等于x的最小的值的下标
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l + 1;//因为使用前缀和,其下标要+1可以不考虑边界问题
}

int main(){
    cin >> n >> m;

    for (int i = 0; i < n; i ++ ){
        int x, c;
        cin >> x >> c;
        add.push_back({x, c});//存入下标即对应的数值c
        alls.push_back(x);//存入数组下标x=add.first
    }

    for (int i = 0; i < m; i ++ ){
        int l, r;
        cin >> l >> r;
        query.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 item : add){ // 处理插入
        int x = find(item.first); // 将add容器的add.secend值存入数组a[]当中,
        a[x] += item.second; // 在去重之后的下标集合alls内寻找对应的下标并添加数值
    }

    for (int i = 1; i <= alls.size(); i ++ ) s[i] = s[i - 1] + a[i]; // 预处理前缀和

    for (auto item : query){ // 处理询问
        int l = find(item.first), r = find(item.second);//在下标容器中查找对应的左右两端[l~r]下标,然后通过下标得到前缀和相减再得到区间a[l~r]的和
        cout << s[r] - s[l - 1] << endl;
    }

    return 0;
}

动态规划

// 一、动态规划————————————背包问题
// 1. 0-1背包
int main(){
    vector<pair<int, int>> goods;
    int n, m;
    cin >> n >> m;
    while(n --){
        int v, w;
        cin >> v >> w;
        goods.push_back({v, w});
    }

    vector<int> dp(m + 1); // 背包容量
    for(auto e : goods)
        for(int i = m; i >= 0; i --)
            if(i - e.first >= 0) dp[i] = max(dp[i], dp[i - e.first] + e.second);

    cout << dp[m];
    return 0;
 }

// 2. 完全背包
// 如果求组合数就是外层物品,内层背包    如果求排列数就是外层背包,内层物品
int main(){
    vector<pair<int, int>> goods;
    int n, m; //物品n个, 背包容量m
    cin >> n >> m;
    while(n --){
        int v, w;
        cin >> v >> w;
        goods.push_back({v, w});
    }

    vector<int> dp(m + 1);
    for(auto e : goods)
        for(int i = 1; i <= m; i ++)
            if(i - e.first >= 0) dp[i] = max(dp[i], dp[i - e.first] + e.second);
    
    cout << dp[m];
    return 0;
}

// 3. 多重背包
/*
有 N 种物品和一个容量是 V 的背包
第 i 种物品最多有 si 件,每件体积是 vi, 价值是 wi
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大, 输出最大价值
*/
const int N = 12000; // log2000取上界+1=12, N≤1000
int v[N], w[N];
int n, m;

int main(){
    cin >> n >> m; // N, V, 用空格隔开, 分别表示物品种数和背包容积
    
    int cnt = 0;
    while(n --){
        int a, b, s; 
        cin >> a >> b >> s; // 接下来有N行,每行三个整数 vi,wi,si, 用空格隔开, 分别表示第i种物品的体积, 价值和数量
        int k = 1; 
        while(k <= s){
            cnt ++; // 可以该物品一个都不取
            v[cnt] = k * a; 
            w[cnt] = k * b;
            s -= k;
            k *= 2;
        }
        if(s > 0){
            cnt ++;
            v[cnt] = s * a;
            w[cnt] = s * b;
        }
    }
    
    vector<int> dp(m + 1); // 转换为0-1背包问题
    for(int i = 0; i <= cnt; i ++)
        for(int j = m; j >= v[i]; j --)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        
    cout << dp[m] << endl;
    return 0;
}

// 4. 分组背包
/*
有 N 组物品和一个容量是 V 的背包. 
每组物品有若干个,同一组内的物品最多只能选一个
每件物品的体积是 vij, 价值是 wij, 其中 i 是组号,j 是组内编号
求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大
*/
const int N = 110;
int v[N][N], w[N][N], s[N];
int dp[N];
int n, m; // 物品组数和背包容量

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) {
        cin >> s[i]; // 表示第 i 个物品组的物品数量
        for (int j = 0; j < s[i]; j ++) cin >> v[i][j] >> w[i][j];
    }
    
    for (int i = 1; i <= n; i ++) // 每一组(一组看成一个大物品)
        for (int j = m; j >= 0; j --) // 大物品0-1背包, 背包倒序遍历
            for (int k = 0; k < s[i]; k ++) 
                if(j >= v[i][k]) dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k]);
    cout << dp[m];
    return 0;
}


// 二、动态规划————————————线性DP
/*
给你一个整数数组 nums ,找到其中最长严格递增子序列的长度
子序列是由数组派生而来的序列,删除（或不删除）数组中的元素而不改变其余元素的顺序
例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列
*/
int lengthOfLIS(vector<int>& nums) {
    vector<int> dp(nums.size(), 1); // 若以nums[0]为结尾,则长度为1
    for(int i = 1; i < nums.size(); i ++)
        for(int j = 0; j <= i; j ++)
            if(nums[i] > nums[i - j])  dp[i] = max(dp[i], dp[i - j] + 1);
    return *max_element(dp.begin(), dp.end());
}

/*
给定两个字符串text1 和 text2, 返回这两个字符串的最长 公共子序列 的长度. 如果不存在 公共子序列, 返回 0 
一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串
例如,"ace" 是 "abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列. 
*/
int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size(), n = text2.size();
    // text1[0, i-1]和空串的最长公共子序列自然是0,所以dp[i][0] = 0; 同理dp[0][j]也是0
    vector<vector<int>> dp(m +1, vector<int>(n + 1, 0)); // dp[i][j] 表示text1前i个数和text2前j个数的最长公共子序列长度
    for(int i = 1; i<= m; i++) {
        for(int j =1; j <=n; j ++) {
            if(text1[i - 1] == text2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            dp[i][j] = max({dp[i][j- 1], dp[i - 1][j], dp[i][j]});
        }
    }
    return dp[m][n];
}


// 三、动态规划————————————区间DP
/*
设有 N 堆石子排成一排,其编号为 1,2,3,…,N
每堆石子有一定的质量,可以用一个整数来描述,现在要将这 N 堆石子合并成为一堆
每次只能合并相邻的两堆,合并的代价为这两堆石子的质量之和,合并后与这两堆石子相邻的石子将和新堆相邻,合并时由于选择的顺序不同,合并的总代价也不相同
例如有 4 堆石子分别为 1 3 5 2,我们可以先合并 1、2 堆,代价为 4 ,得到 4 5 2,又合并 1、2 堆, 代价为 9, 得到 9 2,再合并得到 11, 总代价为 4+9+11=24
如果第二步是先合并 2、3 堆,则代价为 7, 得到 4 7,最后一次合并代价为 11,总代价为 4+7+11=22
*/
const int N = 1e6;
int stones[N];
int n;

int main(){
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> stones[i];
    vector<int> s(n + 1); // 前缀和数组
    for(int i = 1; i <= n; i ++) s[i] = s[i - 1] + stones[i - 1];
    // dp[0][n - 1]表示合并0块 ～ n - 1块石头的最小代价
    vector<vector<int>> dp(n, vector<int>(n)); 
    for(int len = 2; len <= n; len ++){ // 石子堆长度
        for(int start = 0; start + len <= n; start ++){ //石子堆的起点(stones里下标从0开始, 到len - 1)
            int l = start, r = start + len - 1; //len从2开始,若len为1则l==r,只有一块石子,不用合并 
            dp[l][r] = 1e8;
            for(int k = l; k < r; k ++)
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + s[r + 1] - s[l]);
        }
    }
    cout << dp[0][n - 1];
    return 0;
}

搜索与图论

// 一、搜索与图论————————————————————————————————————————————————树与图的存储（领接表）
const int N = 100010, M = N * 2;
int h[N], e[N], ne[N], idx = 0; // 对于每个点k, 开一个单链表, 存储k所有可以走到的点. 

void add(int a, int b) { // 添加一条边 a -> b
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;  
    // h[a] = idx 表示a节点的第一条边编号idx
    // b表示这条边的终点
    // ne[idx] 表示与编号为idx的边同起点的下一条边的编号(上一条边)
}


memset(h, -1, sizeof h); // 初始化

// 二、搜索与图论————————————————————————————————————————————————DFS
int dfs(int u){
    st[u] = true; // st[u] 表示点u已经被遍历过

    for (int i = h[u]; i != -1; i = ne[i]){ // 先选第一条边, 然后选同起点的几条边
        int j = e[i]; 
        if (!st[j]) dfs(j);
    }
}


// 三、搜索与图论————————————————————————————————————————————————BFS
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

while (q.size()){
    int t = q.front();
    q.pop();

    for (int i = h[t]; i != -1; i = ne[i]){ 
        int j = e[i];
        if (!st[j]){
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}


// 四、搜索与图论————————————————————————————————————————————————拓扑排序
const int N = 100010;

int n, m, a, b; // n个节点, m条边
int h[N], e[N], ne[N], idx;
int d[N];
int q[N]; // 模拟队列

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

bool topsort() {
    int hh = 0, tt = -1;

    for (int i = 1; i <= n; i ++ )
        if (!d[i]) q[ ++ tt] = i; // d[i]为 0 表示无入度,肯定是第一个点

    while (hh <= tt) { // !q.empty()
        int t = q[hh ++ ];

        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (-- d[j] == 0) q[ ++ tt] = j;
        }
    }
    // 当队列为空时, BFS搜索结束. 此时如果所有节点都已经入队, 说明图中不存在环, 即拓扑排序成功；否则存在环, 拓扑排序失败. 
    return tt == n - 1;
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);

    for (int i = 0; i < m; i ++ ) {
        cin >> a >> b;
        add(a, b);
        d[b] ++ ; // 在存储过程中, 对每个节点的入度进行统计, 用d数组存储
    }

    if (!topsort()) cout << -1 << endl; // 存在环,无拓扑排序
    else for(int i = 0; i < n; i ++ ) cout << q[i] << " ";

    return 0;
}



// 五、搜索与图论————————————————————————————————————————————————数组建树
class TreeNode {
public:
    TreeNode *left;
    TreeNode *right;
    int val;
    TreeNode() {}
    TreeNode(int val) { this->val = val;}
    TreeNode(TreeNode *left, TreeNode *right, int val) {
        this->left = left;
        this->right = right;
        this->val = val;
    }
};

int main() {
    int n = 10; // 假设n为10
    vector<TreeNode*> nodeList;
    nodeList.push_back(nullptr); // 必须要加, 因为 val=1,left=2,right=3的左右孩子都是第i个节点
    for (int i = 1; i <= n; i ++) nodeList.push_back(new TreeNode(i));
    //                    1       2       3
    int nums[10][2] = {{2, 3}, {4, 5}, {-1, 6}, {7, 8}, {-1, -1}, {9, -1}, {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}}; 
    for (int i = 0; i < n; i ++) {
        nodeList[i + 1]->left = nums[i][0] == -1 ? nullptr : nodeList[nums[i][0]];
        nodeList[i + 1]->right = nums[i][1] == -1 ? nullptr : nodeList[nums[i][1]];
    }
    // 根节点为 nodeList[1];
    return 0;
}


// 六、搜索与图论————————————————————————————————————————————————朴素版 Dijkstra (O n^2  单源最短路, 不存在负权边,稠密图）
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 510;
int n, m;
int g[N][N];
int dist[N];
bool st[N];

int dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    for (int i = 0; i < n - 1 ; i ++ ){
        int t = -1;     // 在还未确定最短路的点中, 寻找离起点距离最小的点
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j;

        // 用t更新其他点的距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }

    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;
}


// 七、搜索与图论————————————————————————————————————————————————堆优化版 Dijkstra (O mlogn  单源最短路, 不存在负权边,稀疏图）
#include <queue>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;

const int N = 150010;
int n, m, a, b, c;      
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储所有点到1号点的距离
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 dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});      // first存储距离, second存储节点编号

    while (heap.size()){
        auto t = heap.top();
        heap.pop();
        
        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i]){ //将这点能达到的所有点的dist更新一遍
            int j = e[i];
            if (dist[j] > distance + w[i]){
                dist[j] = distance + w[i];
                heap.push({dist[j], j}); // 入堆, 方便下一轮选 dist最小 && st为假 的节点
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main() {
    cin >> n >> m;
    memset (h,-1,sizeof (h));
    for (int i = 0; i < m; i ++) {
        cin >> a >> b >> c;
        add(a, b, c);
    }
    cout << dijkstra() << endl;
    return 0;
}


// 八、搜索与图论————————————————————————————————————————————————并查集 
/*
问题1: 如何判断树根? if(p[x] == x)
问题2: 如何求x的集合编号? while(p[x] != x) x = p[x];
问题3: 如何合并两个集合? px是x的集合编号, py是y的集合编号 p[px] = y
*/

// (1)—————————————————————————朴素并查集：
int p[N]; //存储每个点的祖宗节点

// 返回x的祖宗节点 (顺带着并查集路径优化)
int find(int x){  // p[2] = 3,   p[2] = find(3);  
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// 初始化, 假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i;

// 合并a和b所在的两个集合:
p[find(a)] = find(b);

// (2)—————————————————————————维护size的并查集:
int p[N], size[N]; //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义, 表示祖宗节点所在集合中的点的数量

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

// 初始化, 假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i, size[i] = 1;

// 合并a和b所在的两个集合: (我们人为地规定只有根节点的size才有意义)
size[find(b)] += size[find(a)];
p[find(a)] = find(b);

数学

// 一、数学————————————————————————————————————————————————试除法判定素数
bool is_prime(int x){
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0) return false;
    return true;
}


// 二、数学————————————————————————————————————————————————试除法分解质因数
/*
每个合数都可以写成几个质数相乘的形式,其中每个质数都是这个合数的因数
把一个合数用质因数相乘的形式表示出来,叫做分解质因数. 如30 = 2×3×5 分解质因数只针对合数(这里除外)
*/
void divide(int x){
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0) {
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;
        }
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}
/*
30
2 1
3 1
5 1

88  
2 3
11 1
*/


// 二、数学————————————————————————————————————————————————朴素筛法求素数
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n){
    for (int i = 2; i <= n; i ++ ){
        if (!st[i]) {
            primes[cnt ++ ] = i;
            for (int j = i + i; j <= n; j += i)
                st[j] = true;
        }
    }
}


// 二、数学————————————————————————————————————————————————试除法求约数
vector<int> get_divisors(int x){ // 求x的所有约数
    vector<int> res;
    for (int i = 1; i <= x / i; i ++ )
        if (x % i == 0){
            res.push_back(i);
            if (i != x / i) res.push_back(x / i);
        }
    sort(res.begin(), res.end());
    return res;
}


// 二、数学————————————————————————————————————————————————约数个数和约数之和
如果 N = p1^c1 * p2^c2 * ... *pk^ck (分解质因数)
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * (p2^0 + p2^1 + ... + p2^c2) * ... * (pk^0 + pk^1 + ... + pk^ck)


// 二、数学————————————————————————————————————————————————求a,b的最大公约数
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

STL

vector, 变长数组, 倍增的思想
    size()  返回元素个数
    empty()  返回是否为空
    clear()  清空
    front()/back()
    push_back()/pop_back()
    begin()/end()
    []
    支持比较运算, 按字典序

pair<int, int>
    first, 第一个元素
    second, 第二个元素
    支持比较运算, 以first为第一关键字, 以second为第二关键字 (字典序)

string, 字符串
    size()/length()  返回字符串长度
    empty()
    clear()
    substr(起始下标, (子串长度))  返回子串
    c_str()  返回字符串所在字符数组的起始地址

queue, 队列
    size()
    empty()
    push()  向队尾插入一个元素
    front()  返回队头元素
    back()  返回队尾元素
    pop()  弹出队头元素

priority_queue, 优先队列, 默认是大根堆
    size()
    empty()
    push()  插入一个元素
    top()  返回堆顶元素
    pop()  弹出堆顶元素
    定义成小根堆的方式: priority_queue<int, vector<int>, greater<int>> q;

stack, 栈
    size()
    empty()
    push()  向栈顶插入一个元素
    top()  返回栈顶元素
    pop()  弹出栈顶元素

deque, 双端队列
    size()
    empty()
    clear()
    front()/back()
    push_back()/pop_back()
    push_front()/pop_front()
    begin()/end()
    []

set, map, multiset, multimap, 基于平衡二叉树（红黑树）, 动态维护有序序列
    size()
    empty()
    clear()
    begin()/end()
    ++, -- 返回前驱和后继, 时间复杂度 O(logn)

    set/multiset
        insert()  插入一个数
        find()  查找一个数
        count()  返回某一个数的个数
        erase()
            (1) 输入是一个数x, 删除所有x   O(k + logn)
            (2) 输入一个迭代器, 删除这个迭代器
        lower_bound()/upper_bound()
            lower_bound(x)  返回大于等于x的最小的数的迭代器
            upper_bound(x)  返回大于x的最小的数的迭代器
    map/multimap
        insert()  插入的数是一个pair
        erase()  输入的参数是pair或者迭代器
        find()
        []  注意multimap不支持此操作.  时间复杂度是 O(logn)
        lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
    和上面类似, 增删改查的时间复杂度是 O(1)
    不支持 lower_bound()/upper_bound(),  迭代器的++, --

bitset, 圧位
    bitset<10000> s;
    ~, &, |, ^
    >>, <<
    ==, !=
    []

    count()  返回有多少个1

    any()  判断是否至少有一个1
    none()  判断是否全为0

    set()  把所有位置成1
    set(k, v)  将第k位变成v
    reset()  把所有位变成0
    flip()  等价于~
    flip(k) 把第k位取反