dijkstra基础

#include<iostream>

#include<queue>

#include<cstdio>

#include<cstring>

#include<vector>

using namespace std;

#define N 505

#define inf 0x3f3f3f3f

int path[N];//输出路径   存放的是i的前一个点  path[j]=u;

int n,e,m,s;

int vis[N],dis[N],mp[N][N];

int city[N];//为权值   第一优先级为最短路  第二优先级为权值最或者最小 此为第二类权值（和点相连） 还有一种权值为和路相连 那种更简单

int peo[N];

int pathnum[N];//最短路的条数！！！   初始为1   只要在路径相同时累合即可

void dijkstra(int s)

{

    memset(vis,,sizeof vis);

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

        dis[i]=mp[s][i];

    dis[s]=;

    path[s]=-;

    peo[s]=city[s];

    pathnum[s]=;

    //明确规定不加vis[s]

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

    {

        int minn=inf,u=-;

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

            if(!vis[j]&&minn>dis[j])

               minn=dis[u=j];

        if(u==-)return;

        vis[u]=;

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

        {

            if(dis[j]>dis[u]+mp[u][j])

            {

               // pathnum[j]=pathnum[u];//最短路条数

                dis[j]=dis[u]+mp[u][j];

                path[j]=u;

                peo[j]=peo[u]+city[j];

            }

            else if(dis[j]==dis[u]+mp[u][j])

            {

               // pathnum[j]+=pathnum[u];//最短路条数

                if(peo[j]<peo[u]+city[j])

                {

                path[j]=u;

                peo[j]=peo[u]+city[j];

                }

            }

        }

    }

}

void print(int x)

{

   if(path[x]==-)

    {printf("%d",x);return;}

   print(path[x]);

    printf(" %d",x);

    return ;

}

int main()

{

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

    for(int i=;i<n;i++)scanf("%d",&city[i]);

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

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

      mp[i][j]=inf;//如果加上 i==j 时mp为0  则可以反复刷权值

     while(m--)

     {

         int a,b,c;

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

         if(mp[a][b]>c)mp[a][b]=mp[b][a]=c;

     }

     dijkstra(s);

     printf("%d %d\n", pathnum[e] ,peo[e] );

     print(e);

    return ;

}

用堆优化

#include<bits/stdc++.h>

using namespace std;

//input by bxd

#define rep(i,a,b) for(int i=(a);i<=(b);i++)

#define repp(i,a,b) for(int i=(a);i>=(b);--i)

#define RI(n) scanf("%d",&(n))

#define RII(n,m) scanf("%d%d",&n,&m)

#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)

#define RS(s) scanf("%s",s);

#define ll long long

#define REP(i,N)  for(int i=0;i<(N);i++)

#define CLR(A,v)  memset(A,v,sizeof A)

//////////////////////////////////

#define inf 0x3f3f3f3f

#define INF 0x3f3f3f3f

#define N 3000

int head[N];

int pos;

struct node

{

    int  v,to,nex;

}edge[N<<];

void add(int a,int b,int c)

{

    edge[++pos].nex=head[a];

    head[a]=pos;

    edge[pos].v=c;

    edge[pos].to=b;

}

struct Node

{

    int d,id;

    bool operator<(Node b)const

    {

        return d>b.d;

    }

};

int n;

int dis[N],vis[N];

void dijkstra(int s)

{

    rep(i,,n)

    dis[i]=inf;

    dis[s]=;

    priority_queue<Node>q;

    q.push(Node{,s});

    while(!q.empty())

    {

        Node u=q.top();q.pop();

        if(vis[u.id])continue;

        vis[u.id]=;

        for(int i=head[u.id];i;i=edge[i].nex)

        {

            int v=edge[i].to;

            if(u.d+edge[i].v<dis[v])

            {

                dis[v]=u.d+edge[i].v;

                q.push(Node{dis[v],v});

            }

        }

    }

}

int main()

{

    int m,s,t;

    RII(n,m);RII(s,t);

    while(m--)

    {

        int a,b,c;

        RIII(a,b,c);

        add(a,b,c);

        add(b,a,c);

    }

    dijkstra(s);

    cout<<dis[t];

    return ;

}