最短路

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 42527    Accepted Submission(s): 18622

2 1

1 2 3

3 3

1 2 5

2 3 5

3 1 2

0 0

3

2

求特定起点的到终点的最小值，取距离当前起点近期的点为中间点，比較起点到其它点的距离与起点到中间点的距离加上中间点到其它点的距离之和的大小，更新起点到其它点的最小值，以得到起点到终点的最小值

dijkstra

#include <iostream>

#include<cstdio>

#include<cstring>

#define inf 0x3f3f3f3f

using namespace std;

int n,map[110][110];

int vis[110],rec[110];

void dijkstra(int s,int e)

{

    int minw,mark;

    memset(vis,0,sizeof(vis));

    vis[s]=1;

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

        rec[i]=map[s][i];

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

    {

        minw=inf;

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

        {

            if(!vis[j]&&rec[j]<minw)

            {

                minw=rec[j];

                mark=j;

            }

        }

        vis[mark]=1;

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

        {

            if(!vis[j]&&rec[j]>rec[mark]+map[mark][j])

                rec[j]=rec[mark]+map[mark][j];

        }

    }

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

}

int main()

{

    int m,a,b,v;

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

    {

        memset(map,inf,sizeof(map));

        while(m--)

        {

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

            if(v<map[a][b])

                map[a][b]=map[b][a]=v;

        }

        dijkstra(1,n);

    }

    return 0;

}

求随意两点间的最短距离。任取中间点不断更新最小值

floyed

#include<iostream>

#include<cstdio>

#include<cstring>

#define inf 0x3f3f3f3f

using namespace std;

int n,map[110][110];

void floyed()

{

    for(int k=1;k<=n;++k)

    {

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

        {

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

            {

                if(map[i][j]>map[i][k]+map[k][j])

                    map[i][j]=map[i][k]+map[k][j];

            }

        }

    }

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

}

int main()

{

    int m,a,b,v;

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

    {

        memset(map,inf,sizeof(map));

        while(m--)

        {

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

            if(v<map[a][b])

                map[a][b]=map[b][a]=v;

        }

        floyed();

    }

    return 0;

}

第一篇SPFA。參照宇神模板

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#define maxn 110

#define maxm 20000+20

#define inf 0x3f3f3f

using namespace std;

int n,m,cnt,head[maxn],rec[maxn],vis[maxn];

struct node

{

    int from,to,val,next;

};

node edge[maxm];

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

{

    edge[cnt].from=a;

    edge[cnt].to=b;

    edge[cnt].val=c;

    edge[cnt].next=head[a];

    head[a]=cnt++;

}

void initialize()

{

    cnt=0;

    memset(head,-1,sizeof(head));

}

void getmap()

{

    int a,b,c;

    while(m--)

    {

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

        add(a,b,c);

        add(b,a,c);

    }

}

void spfa(int s)

{

    queue<int>q;

    memset(vis,0,sizeof(vis));//记录已在队列中的点

    memset(rec,inf,sizeof(rec));//记录最短距离

    rec[s]=0;

    vis[s]=1;

    q.push(s);

    while(!q.empty())

    {

        int u=q.front();

        q.pop();

        vis[u]=0;//该点之后还可能进入队列

        for(int i=head[u];i!=-1;i=edge[i].next)

        {

            int v=edge[i].to;

            if(rec[v]>rec[u]+edge[i].val)

            {

                rec[v]=rec[u]+edge[i].val;

                if(!vis[v])

                {

                    q.push(v);//该点若不在队列中，更新过的rec[v]可能会影响其它点的最短距离所以在进入队列

                    vis[v]=1;

                }

            }

        }

    }

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

}

int main()

{

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

    {

        initialize();

        getmap();

        spfa(1);

    }

    return 0;

}