Dijskstra算法

采用优先队列优化

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e5+;

const int maxm=1e6+;

int head[maxn],ver[maxm],edge[maxm],nxt[maxm],d[maxn];

int tot;

int v[maxn];

int n,m;

const int INF=0x3f3f3f3f;

priority_queue<pair<int,int> > q;

void add(int x,int y,int z)

{

    ver[++tot]=y;

    edge[tot]=z;

    nxt[tot]=head[x];

    head[x]=tot;

}

void dij()

{

    memset(d,INF,sizeof(d));

    memset(v,,sizeof(v));

    d[]=;

    q.push(make_pair(,));

    while(q.size())

    {

        int x=q.top().second;

        q.pop();

        if(v[x]) continue;

        v[x]=;

        for(int i=head[x]; i; i=nxt[i])

        {

            int y=ver[i];

            int z=edge[i];

            if(d[y]>d[x]+z)

            {

                d[y]=d[x]+z;

                q.push(make_pair(-d[y],y));

            }

        }

    }

}

int main()

{

    int n,m;

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

    {

        tot=;

        memset(head,,sizeof(head));

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

        {

            int x,y,z;

            scanf("%d%d%d",&x,&y,&z);

            add(x,y,z);

            add(y,x,z);

        }

        dij();

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

    }

}

//6 9

//1 2 1

//1 3 12

//2 3 9

//2 4 3

//3 5 5

//4 3 4

//4 5 13

//4 6 15

//5 6 4

//

//0 1 8 4 13 17

#include <cstdio>

#include <queue>

#include <vector>

using namespace std;

const int maxn = ;

const int INF = <<;

struct node

{

    int x,d;

    node() {}

    node(int a,int b)

    {

        x=a;

        d=b;

    }

    bool operator < (const node & a) const

    {

        if(d==a.d) return x<a.x; // 按d从小到大，x从大到小自动排序

        else return d > a.d;

    }

};

vector<node> eg[maxn];

int dis[maxn],n;

void Dijkstra(int s)

{

    int i;

    for(i=; i<=n; i++) dis[i]=INF;

    dis[s]=;

    //用优先队列优化，就是个堆

    priority_queue<node> q;

    q.push(node(s,dis[s]));

    while(!q.empty())

    {

        node x=q.top();

        q.pop();

        for(i=; i<eg[x.x].size(); i++)

        {

            node y=eg[x.x][i];

            if(dis[y.x]>x.d+y.d)

            {

                dis[y.x]=x.d+y.d;

                q.push(node(y.x,dis[y.x]));

            }

        }

    }

}

int main()

{

    int a,b,d,m;

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

    {

        for(int i=; i<=n; i++) eg[i].clear();

        while(m--)

        {

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

            eg[a].push_back(node(b,d));

            eg[b].push_back(node(a,d));

        }

        Dijkstra();

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

            printf("%d ", dis[i]);

    }

    return ;

}

//6 9

//1 2 1

//1 3 12

//2 3 9

//2 4 3

//3 5 5

//4 3 4

//4 5 13

//4 6 15

//5 6 4

//

//0 1 8 4 13 17

朴素版本，时间复杂度比上面的要高

#include<cstdio>

int e[][];

int dis[];

int book[];

int main()

{

    int n, m;

    int inf=;

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

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

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

            if(i==j)

                e[i][j]=;

            else

                e[i][j]=inf;

    int t1, t2, t3;

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

    {

        scanf("%d%d%d", &t1, &t2, &t3);

        e[t1][t2]=t3;

    }

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

    {

        dis[i]=e[][i];

    }

    int u, min;

    book[]=;

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

    {

        min=inf;

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

        {

            if(dis[j]<min && book[j]==)

            {

                u=j;

                min=dis[j];

            }

        }

        book[u]=;

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

        {

            if(e[u][v]<inf && dis[v]>dis[u]+e[u][v])

            {

                dis[v]=dis[u]+e[u][v];

            }

        }

    }

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

        printf("%d ", dis[i]);

}