【最短路模板】floyd dijkstra 链式前向星 + 优先队列 spfa

floyd 多源多汇最短路

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxx=0x3f3f3f3f;
 4 int mp[150][150];
 5 int nodenum,edgenom;
 6 int floyd(int scr,int des)///多源多汇最短路
 7 {
 8     for(int k=1;k<=nodenum;k++)
 9     {
10         for(int i=1;i<=nodenum;i++)
11         {
12             for(int j=1;j<=nodenum;j++)
13             {
14                 mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
15             }
16         }
17     }
18     return mp[scr][des];
19 }
20 int main()
21 {
22     int start,endd,cost;
23     while(scanf("%d %d",&nodenum,&edgenom)&&(nodenum+edgenom))
24     {
25         for(int i=1;i<=nodenum;++i)
26         {
27             for(int j=1;j<=nodenum;++j)
28             {
29                 mp[i][j]=maxx;
30             }
31         }
32         for(int i=1;i<=edgenom;++i)
33         {
34             scanf("%d %d %d",&start,&endd,&cost);
35             mp[start][endd]=min(mp[start][endd],cost);
36             mp[endd][start]=min(mp[endd][start],cost);
37         }
38         cout<<floyd(1,nodenum)<<'
';
39     }
40     return 0;
41 }

迪杰斯特拉普通版本：

#include <bits/stdc++.h>
using namespace std;
const int maxx=0x3f3f3f3f;
int mp[150][150];
int dis[150];
bool vis[150];
int nodenum,edgenom;
int dijkstra(int scr,int des)
{
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=nodenum;++i)
    {
        dis[i]=mp[scr][i];
    }
    dis[scr]=0;
    vis[scr]=1;
    for(int i=1;i<=nodenum;i++)
    {
        int tmp=maxx;
        int k;
        for(int j=1;j<=nodenum;j++)
        {
            if(!vis[j]&&tmp>dis[j])
            {
                tmp=dis[j];
                k=j;
            }
        }
        if(tmp==maxx)
        {
            break;
        }
        vis[k]=1;
        for(int j=1;j<=nodenum;j++)
        {
            if(!vis[j]&&dis[j]>dis[k]+mp[k][j])
            {
                dis[j]=dis[k]+mp[k][j];
            }
        }
    }
    return dis[des];
}
int main()
{
    int start,endd,cost;
    while(scanf("%d %d",&nodenum,&edgenom)&&(nodenum+edgenom))
    {
        for(int i=1;i<=nodenum;++i)
        {
            for(int j=1;j<=nodenum;++j)
            {
                mp[i][j]=maxx;
            }
        }
        for(int i=1;i<=edgenom;++i)
        {
            scanf("%d %d %d",&start,&endd,&cost);
            mp[start][endd]=min(mp[start][endd],cost);
            mp[endd][start]=min(mp[endd][start],cost);
        }
        cout<<dijkstra(1,nodenum)<<'
';
    }
    return 0;
}

迪杰斯特拉链式前向星 + 优先队列

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=30000;
int head[maxn];
bool vis[150];
int dis[150];
int nodenum,edgenom,tot;
struct edge
{
    int u,v,l,next;
}t[maxn];
struct A
{
    int pos,cost;
    bool operator < (const A &a)const{
        return cost>a.cost;
    }
};
void addedge(int x,int y,int z)
{
    t[tot].u=x;
    t[tot].v=y;
    t[tot].l=z;
    t[tot].next=head[x];
    head[x]=tot++;
}
int dijkstra(int src,int des)///scorce,destination
{
    memset(dis,INF,sizeof(dis));
    memset(vis,0,sizeof(vis));
    priority_queue<A>q;
    dis[src]=0;
    A now;
    now.cost=0;
    now.pos=src;
    q.push(now);
    while(!q.empty())
    {
        now=q.top();
        q.pop();
        if(vis[now.pos])
        {
            continue;
        }
        vis[now.pos]=1;
        for(int i=head[now.pos];~i;i=t[i].next)
        {
            int to=t[i].v;
            if(!vis[to]&&dis[to]>t[i].l+dis[t[i].u])///dis[t[i].v]>dis[t[i].u]+t[i].l            {
                dis[to]=dis[t[i].u]+t[i].l;
                now.cost=dis[to];
                now.pos=to;
                q.push(now);
            }
        }
    }
    return dis[des];
}
int main()
{
    int start,endd,cost;
    while(scanf("%d %d",&nodenum,&edgenom)&&(nodenum+edgenom))
    {
        tot=0;
        memset(head,-1,sizeof(head));
        for(int i=1;i<=edgenom;++i)
        {
            scanf("%d %d %d",&start,&endd,&cost);
            addedge(start,endd,cost);
            addedge(endd,start,cost);
        }
//        for(int i=0;i<tot;i++)
//        {
//            cout<<t[i].u<<' '<<t[i].v<<' '<<t[i].l<<'
';
//        }
        cout<<dijkstra(1,nodenum)<<'
';
    }
    return 0;
}

spfa 链式前向星

 1 #include <bits/stdc++.h>
 2 #define INF 0x3f3f3f3f
 3 using namespace std;
 4 const int maxn=30000;
 5 int head[maxn];
 6 int cnt[150];
 7 bool vis[150];
 8 int dis[150];
 9 int nodenum,edgenom,tot;
10 struct edge
11 {
12     int u,v,l,next;
13 }t[maxn];
14 void addedge(int x,int y,int z)
15 {
16     t[tot].u=x;
17     t[tot].v=y;
18     t[tot].l=z;
19     t[tot].next=head[x];
20     head[x]=tot++;
21 }
22 int spfa(int src,int des)///scorce,destination
23 {
24     memset(dis,INF,sizeof(dis));
25     memset(vis,0,sizeof(vis));
26     memset(cnt,0,sizeof(cnt));
27     queue<int>q;
28     dis[src]=0;
29     vis[src]=1;
30     q.push(src);
31     while(!q.empty())
32     {
33         int now=q.front();
34         q.pop();
35         if(++cnt[now]>nodenum)
36         {
37             return 0;
38         }
39         vis[now]=0;
40         for(int i=head[now];~i;i=t[i].next)
41         {
42             if(dis[t[i].v]>t[i].l+dis[now])///能更新就更新
43             {
44                 dis[t[i].v]=t[i].l+dis[now];
45                 if(!vis[t[i].v])
46                 {
47                     vis[t[i].v]=1;
48                     q.push(t[i].v);
49                 }
50             }
51         }
52     }
53     return 1;
54 }
55 int main()
56 {
57     int start,endd,cost;
58     while(scanf("%d %d",&nodenum,&edgenom)&&(nodenum+edgenom))
59     {
60         tot=0;
61         memset(head,-1,sizeof(head));
62         for(int i=1;i<=edgenom;++i)
63         {
64             scanf("%d %d %d",&start,&endd,&cost);
65             addedge(start,endd,cost);
66             addedge(endd,start,cost);
67         }
68         if(!spfa(1,nodenum))
69         {
70             cout<<"-1"<<'
';
71         }
72         else
73         {
74             cout<<dis[nodenum]<<'
';
75         }
76     }
77     return 0;
78 }