藍橋杯 算法訓練---最短路（spfa算法）

本題一開始用dijkstra寫的，，逾時，，結果隻得了70分，，後來想到了用spfa寫，，無奈不太熟悉，，就查了一下題解，感覺還行，，不過學到了一種新的stl知識—容器，，有關容器的介紹我寫在了–我的個人總結….下面是我的逾時代碼和AC代碼。

逾時代碼：

#include<cstdio>
#include<iostream>
#define MAXN 1005
using namespace std;

int e[2005][2005],dis[2005],book[2005],i,j,m,n,t1,t2,t3,u,v,minx;
int main()
{
    int inf=100001;
    while(~scanf("%d %d",&n,&m))
    {
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=n; j++)
            {
                if(i==j) e[i][j]=0;
                else e[i][j]=inf;
            }
        }
        for(i=1; i<=m; i++)
        {
            scanf("%d %d %d",&t1,&t2,&t3);
            e[t1][t2]=t3;
        }

        for(i=1; i<=n; i++)
        {
            dis[i]=e[1][i];
        }

        for(i=1; i<=n; i++)
        {
            book[i]=0;
        }
        book[1]=1;
        for(i=1; i<=n-1; i++)
        {
            minx=inf;
            for(j=1; j<=n; j++)
            {
                if(book[j]==0&&dis[j]<minx)
                {
                    minx=dis[j];
                    u=j;
                }
            }
            book[u]=1;
            for(v=1; v<=n; v++)
            {
                if(e[u][v]<inf)
                {
                    if(dis[v]>dis[u]+e[u][v])
                    {
                        dis[v]=dis[u]+e[u][v];
                    }
                }
            }
        }

        for(i=2; i<=n; i++)
        {
            printf("%d\n",dis[i]);
        }
    }
    return 0;
}           

AC代碼：

#include<iostream>
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
#define inf 99999999
typedef struct minx
{
    int a,d;
}node;
int dis[20005],n;
vector<node>map[20005];
void init()
{
    for(int i=1;i<=n;i++)
    {
        dis[i]=inf;
    }
}

void spfa()
{
    queue<int>q;
    int book[20005]={0},t;
    q.push(1);
    book[1]=1;
    dis[1]=0;
    while(!q.empty())
    {
        t=q.front();
        q.pop();
        book[t]=0;
        int len=map[t].size(),a;//map[t].size（）傳回的是map[t]的長度
        for(int i=0;i<len;i++)
        {
            a=map[t][i].a;//map[t][i].a代表與map[t][i]相連的路
            if(dis[a]>map[t][i].d+dis[t])
            {
                dis[a]=map[t][i].d+dis[t];//map[t][i].d代表a到與其相連的路的距離
                if(!book[a])//若果a還沒有通路過，a入隊
                   {
                        book[a]=1;
                            q.push(a);
                   }
            }
        }
    }
}
int main()
{
    int m,a,b,l;
    node NOW;
    while(~scanf("%d%d",&n,&m))
    {
        init();
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&l);
            NOW.a=b;NOW.d=l;//對其進行整理規範
            map[a].push_back(NOW);//将整理規範後的結果讀取到容器裡.
        }
        spfa();
        for(int i=2;i<=n;i++)
            printf("%d\n",dis[i]);
    }
    return 0;
}
           

如果有什麼寫錯的地方，，及時告訴我哦，，我是很樂意接受别人的指導的……….