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