魔法效果——dijkstra+堆（邻接表存储）

dijkstra本身每次要for一遍，才能找出最小的节点，但用了堆之后，直接取出堆首就可以了。

但要注意的一点是，c++自带的stl里的priority_queue本身是先入大出的，而我们要求的是最小值，所以我们在push的时候是插入负数，这样就能保证是先入小出的了

代码如下：

各种定义：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define MAXN 300000

using namespace std;

int edge,n,m,u,a,b,c;

int head[MAXN],to[MAXN],next[MAXN],w[MAXN];

int used[MAXN];

struct data

{

    int d,num;

    friend bool operator<(const data &a,const data &b)

    {

        return a.d>b.d;

    }

}dis[MAXN];

priority_queue<data>team;

void build(int a,int b,int c) //建表

{

    edge++;

    next[edge]=head[a];

    w[edge]=c;

    to[edge]=b;

    head[a]=edge;

} 

主函数

scanf("%d%d",&n,&m);

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

    {

        scanf("%d%d%d",&a,&b,&c);

        build(a,b,c);

    }

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

    {

        dis[i].d=0x7fffffff/;
        dis[i].num=i; //赋初始值

    }

//dijkstra+堆的主要代码
    dis[].d=;//把它的边做的最小

    team.push(dis[]);//插入这个节点
    while(!team.empty())//非空

    {

        data t=team.top();

        team.pop();

        int u=t.num;

        if(used[u])continue;

        used[u]=;

        for(int i=head[u];i;i=next[i])

    {

        if(dis[to[i]].d>dis[u].d+w[i])

        {

            dis[to[i]].d=dis[u].d+w[i];

            team.push(dis[to[i]]);

        }

    }

}

    if(dis[n].d!=0x7fffffff/)cout<<dis[n].d;

    else cout<<-; 

神奇吧，我也觉得很神奇！

据说这样写可以把时间降低到比spfa还要快，好厉害！！！（果然是魔法操作）