链式前向星实现的堆优化dij求最短路模板

#include<cstdio>

#include<string>

#include<cstdlib>

#include<cmath>

#include<iostream>

#include<cstring>

#include<set>

#include<queue>

#include<algorithm>

#include<vector>

#include<map>

#include<cctype>

#include<stack>

#include<sstream>

#include<list>

#include<assert.h>

#include<bitset>

#include<numeric>

#define debug() puts("++++")

#define gcd(a,b) __gcd(a,b)

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define fi first

#define se second

#define pb push_back

#define sqr(x) ((x)*(x))

#define ms(a,b) memset(a,b,sizeof(a))

#define sz size()

#define be begin()

#define pu push_up

#define pd push_down

#define cl clear()

#define lowbit(x) -x&x

#define all 1,n,1

#define rep(i,x,n) for(int i=(x); i<(n); i++)

#define in freopen("in.in","r",stdin)

#define out freopen("out.out","w",stdout)

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

typedef pair<int,int> P;

const int INF = 0x3f3f3f3f;

const LL LNF = 1e18;

const int maxn = 1e5+;

const int maxm = 1e6+;

const double PI = acos(-1.0);

const double eps = 1e-;

const int dx[] = {-,,,,,,-,-};

const int dy[] = {,,,-,,-,,-};

int dir[][] = {{,},{,-},{-,},{,}};

const int mon[] = {, , , , , , , , , , , , };

const int monn[] = {, , , , , , , , , , , , };

int head[maxn],vis[maxn],dis[maxn];

int t,n,m,u,v,w,st,ed;

struct node

{

    int v,w,nxt;

}e[maxn<<];

/*struct cmp

{

    bool operator()(int a,int b)

    {

        return dis[a]>dis[b];

    }

};*/

int tot=;

void init()

{

    tot=;

    ms(head,-);

    ms(vis,);

    ms(dis,INF);

}

void add(int u,int v,int w)

{

    e[tot].v=v;

    e[tot].w=w;

    e[tot].nxt=head[u];

    head[u]=tot++;

}

void dij(int s,int t)

{

    priority_queue< pair<int,int> > q;

    dis[s]=;

    q.push(make_pair(,s));

    while(!q.empty())

    {

        int u = q.top().second;

        q.pop();

        for(int i=head[u];i!=-;i=e[i].nxt)

        {

            int v = e[i].v;

            if(dis[v]>dis[u]+e[i].w)

            {

                dis[v]=dis[u]+e[i].w;

                q.push(make_pair(-dis[v],v));

            }

        }

    }

    int ans=dis[t];

    if(ans!=INF)

        printf("%d\n",ans);

    else puts("-1");

}

int main()

{

    while(~scanf("%d%d",&n,&m))

    {

        init();

        for(int i=;i<m;i++)

        {

            scanf("%d%d%d",&u,&v,&w);

            add(u,v,w);

            add(v,u,w);

        }

        scanf("%d%d",&st,&ed);

        dij(st,ed);

    }

}

/*

【题意】

【类型】

【分析】

【时间复杂度&&优化】

【trick】

【数据】

*/