目录
//二叉小顶堆-优先队列
#include <iostream>
#define Max_N 1010
using namespace std;
int Heap_size;
int Heap[Max_N];
//插入操作
void push(int x)
{
int indx=++Heap_size;//首先插入到最后一个位置
//向上调整
while(indx>1)//只有i>1才会有父节点
{
int parent_indx=indx/2;//父节点编号
if(Heap[parent_indx]<=x)//没有上下颠倒就结束调整
break;
Heap[indx]=Heap[parent_indx];//大小颠倒就将当前节点上调
indx=parent_indx;
}
Heap[indx]=x;
}
//删除操作
int pop()
{
int result=Heap[0];//获取最值
int x=Heap[--Heap_size];//相当于将最后的一个元素放到根节点
int index=1;
while(2*index<=Heap_size)//一定要有子节点
{
int L_son_index=2*index;
int R_son_index=2*index+1;
//比较儿子节点的最值
int Min_index=L_son_index;
if(R_son_index<=Heap_size && Heap[R_son_index]<Heap[Min_index])
Min_index=R_son_index;
//如果没有上下颠倒就结束
if(Heap[Min_index]>=x)
break;
//上下颠倒就交换
Heap[index]=Heap[Min_index];
index=Min_index;
}
Heap[index]=x;
return result;
}
void Build_Heap(int data[],int n)
{
//创建一个空堆
Heap_size=0;
for(int i=0;i<n;i++)//逐个插入元素
push(data[i]);
}
int main()
{
int n;
int data[Max_N];
cin>>n;
for(int i=0;i<n;i++)
cin>>data[i];
for(int i=0;i<n;i++)
cout<<data[i]<<" ";
cout<<endl;
Build_Heap(data,n);
for(int i=1;i<=Heap_size;i++)
cout<<Heap[i]<<" ";
cout<<endl;
return 0;
}
#include<stdio.h>
#include<algorithm>
#include<queue>
#define INF 2147483647
using namespace std;
typedef pair<int,int> pii;
int u[150000],v[150000],w[150000],next[150000],first[150000],n,m,d[150000], tot;
int maxn[21];
bool done[150000];
priority_queue<pii,vector<pii>,greater<pii> >q;
void addedge(int st, int end, int val)
{
u[++tot] = st;
v[tot] = end;
w[tot] = val;
next[tot] = first[st];
first[st] = tot;
}
void dij(int a)
{
int i;
for(i = 1; i <= n; i++)d[i] = INF;
d[a] = 0;
q.push(make_pair(d[a],a));
while(!q.empty())
{
int x = q.top().second;q.pop();
if(done[x])continue;
done[x] = true;
for(int e = first[x];e != -1; e = next[e])
if(d[v[e]] > d[x] + w[e])
{
d[v[e]] = d[x] + w[e];
q.push(make_pair(d[v[e]], v[e]));
}
}
}
int main()
{
int i;
scanf("%d%d", &n, &m);
for(i = 1; i <= n; i++)first[i] = -1;
for(i = 1; i <= m; i++)
{
int st,end,val;
scanf("%d%d%d", &st, &end, &val);
addedge(st, end, val);
addedge(end, st, val);
}
dij(1);
printf("%d ", d[3]);
return 0;
}