Dijkstra求最短路 I

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 −1。
数据范围
1≤n≤500,
1≤m≤10^5,
图中涉及边长均不超过10000。
输入样例：

3 3
1 2 2
2 3 1
1 3 4

输出样例：

3

思路：稠密图，点少边多，并且数据量小，可以用朴素的dijkstra来求，用邻接矩阵存储。

#include<bits/stdc++.h>
using namespace std;
const int N = 5e2+10;
int g[N][N];
bool st[N];
int dist[N];
int n,m;
int dijkstra(){
    memset(dist,0x3f3f3f3f,sizeof dist);
    //需要重新赋值为0
    dist[1]=0;
    //dist下标从0开始，g下标从1开始
    for(int i=0;i<n;i++){
        int t = -1;
        for(int j=1;j<=n;j++){
            if(!st[j]&&(t==-1||dist[t]>dist[j]))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,0x3f3f3f3f,sizeof g);
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]= min(g[a][b],c);
    }
    
    cout<<dijkstra()<<'\n';
    return 0;
}

堆排序

输入一个长度为 n 的整数数列，从小到大输出前 m 小的数。
输入格式
第一行包含整数 n 和 m。
第二行包含 n 个整数，表示整数数列。
输出格式
共一行，包含 m 个整数，表示整数数列中前 m 小的数。
数据范围
1≤m≤n≤10^5，
1≤数列中元素≤10^9
输入样例：

5 3
4 5 1 3 2

输出样例：

1 2 3

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,m,_size;
int h[N];

void down(int u){
    int t = u;
    //获取三个数中最小数的下标
    if(2*u<=_size&&h[2*u]<h[t])t=2*u;
    if(2*u+1<=_size&&h[2*u+1]<h[t])t=2*u+1;
    if(u!=t){
        swap(h[t],h[u]);
        down(t);
    }
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>h[i];
    _size = n;
    //1先要整体down一遍第一个才能使最小
    //2n/2是最大的非叶子结点
    for(int i=n/2;i;i--)down(i);
    //时间复杂度是mlogn
    while(m--){
        cout<<h[1]<<" ";
        h[1]=h[_size--];
        down(1);
    }
    return 0;
}

模拟堆

维护一个集合，初始时集合为空，支持如下几种操作：

• I x，插入一个数 x；
• PM，输出当前集合中的最小值；
• DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
• D k，删除第 k个插入的数；
• C k x，修改第 k 个插入的数，将其变为 x；

现在要进行 N 次操作，对于所有第 2 个操作，输出当前集合的最小值。
输入格式
第一行包含整数 N。
接下来 N 行，每行包含一个操作指令，操作指令为 I x，PM，DM，D k 或 C k x 中的一种。
输出格式
对于每个输出指令 PM，输出一个结果，表示当前集合中的最小值。
每个结果占一行。
数据范围
1≤N≤10^5
−10^9≤x≤10^9
数据保证合法。
输入样例：

8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM

输出样例：

-10
6

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

const int N = 1e5+10;
//h[k]=x表示堆中下标为k的元素值为x；
//hp[k]=x表示堆中下标为k的元素，是第x个插入；
//ph[k]=x表示堆中第k个插入的元素，下标为x；
int h[N],ph[N],hp[N],_size;

void heap_swap(int u,int v){
    swap(ph[hp[u]], ph[hp[v]]);
    swap(hp[u],hp[v]);
    swap(h[u],h[v]);
}

void down(int u){
    int t = u;
    if(2*u<=_size&&(h[2*u]<h[t]))t=2*u;
    if(2*u+1<=_size&&(h[2*u+1]<h[t]))t=2*u+1;
    if(t!=u){
        heap_swap(u, t);
        down(t);
    }
}

void up(int u){
    while(u/2&&h[u/2]>h[u]){
        heap_swap(u/2, u);
        u/=2;
    }
}


int main(){
    int n,m=0;
    cin>>n;
    while(n--){
        int x,k;
        char op[10];
        cin>>op;
        if(!strcmp(op,"I")){
            cin>>x;
            ++_size;
            ++m;
            h[_size]=x;
            ph[m]=_size,hp[_size]=m;
            up(_size);
        }
        else if(!strcmp(op, "PM"))cout<<h[1]<<endl;
        else if(!strcmp(op, "DM")){
            heap_swap(1, _size);
            _size--;
            down(1);
        }
        else if(!strcmp(op, "D")){
            cin>>k;
            //必须要将第k个插入堆中的下标数x保存
            //因为swap后x会变化，为原_size
            k=ph[k];
            heap_swap(k, _size);
            _size--;
            down(k),up(k);
        }
        else{
            cin>>k>>x;
            h[ph[k]]=x;
            down(ph[k]),up(ph[k]);
        }
    }
    return 0;
}

如果你努力了，但是事情并没有多大的改变，并不能证明你没有用，而是代表你在赎罪，你总得为你过去的懒散付出点代价，这个时候你应该更加努力而不是消沉下去，欠的账总会还完，日子总会阳光明媚的，很多人看似输掉的是结果，而本质上输掉的是过程，人生没有白走的路，也没有白读的书，好运都是努力的伏笔，哪怕乌云密布，继续攀爬就是晴空万里，所以，请继续努力。
------《人民日报》