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);//需要重新赋值为0dist[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);//时间复杂度是mlognwhile(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会变化，为原_sizek=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;
}

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