Dijkstra+Priority_Queue

//二叉小顶堆-优先队列
#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;
}