题目描述

有一个邮递员要送东西，邮局在节点1.他总共要送N-1样东西，其目的地分别是2~N。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有M条道路，通过每条道路需要一定的时间。这个邮递员每次只能带一样东西。求送完这N-1样东西并且最终回到邮局最少需要多少时间。

思路

正着跑一边，把边倒过来跑一边就可以了
O(n^2)

#include 
#define maxn 3001
#define INF 0x7f7f7f7f
int a[maxn][maxn],d[7001],f[7001],dd[maxn],fl[maxn],aa[maxn][maxn];
int main()
{
    int n,m,s,e;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
        {
            a[i][j]=INF;
            aa[i][j]=INF;
        }
    for (int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        if (z            a[x][y]=z;
        if (z            aa[y][x]=z;
    }
    f[1]=1; fl[1]=1;
    for (int i=1;i<=n;i++)
    {
        d[i]=a[1][i];
        dd[i]=aa[1][i];
    }
    int u=0,u1=0;
    do
    {
        u=0;
        int mi=INF;
        for (int i=1;i<=n;i++)
        {
            if (f[i]==0&&d[i]            {
                u=i;
                mi=d[i];
            }
        }
        if (u!=0)
        {
            f[u]=1;
            for (int i=1;i<=n;i++)
            {
                if (f[i]==0&&d[u]+a[u][i]                {
                    d[i]=d[u]+a[u][i];
                }
            }
        }
    }
    while (u!=0);
    do 
    {
        u1=0;
        int min=INF;
        for (int i=1;i<=n;i++)
        {
            if (fl[i]==0&&dd[i]            {
                u1=i;
                min=dd[i];
            }
        }
        if (u1!=0)
        {
            fl[u1]=1;
            for (int i=1;i<=n;i++)
            {
                if (fl[i]==0&&dd[u1]+aa[u1][i]                {
                    dd[i]=dd[u1]+aa[u1][i];
                }
            }
        }
    }
    while (u1!=0);
    int ans=0;
    for (int i=2;i<=n;i++) ans+=d[i]+dd[i];
    printf("%d\n",ans);
}