poj3268---spfa

最短路径。。。。
由于点比较多1000，，如果dijstra算法 o（n^2）肯定超时，这里用spfa算法。
由于1000点，没有用邻接表，内存略大。

算法很简单，还是正向建图，逆向建图，分别求出起点到其他点的最短距离，然后求和，就是从这点出发，然后再回来的的最短距离，最后求出最大值即可。
代码：
[cpp]
#include<stdio.h>

#define maxN 1001
#define inf 100000000

int n, x, m;
int mat[maxN][maxN];    //正向图邻接矩阵
bool flag[maxN][maxN]; //正向图标志矩阵
int re_mat[maxN][maxN]; //逆向图邻接矩阵
bool re_flag[maxN][maxN];//逆向图标示矩阵
int dis[maxN];      //起点到其他点的最短路径
int disRes[maxN];   //往返最短路径和
bool vis[maxN];     //标示那个点在队列中
int queue[10 * maxN];//spfa队列

//邻接矩阵初始化
void Init()
{
    for (int i = 1; i <= n; ++ i)
    {
        for (int j = 1; j <= n; ++ j)
        {
            mat[i][j] = inf;
            flag[i][j] = false;
            re_mat[i][j] = inf;
            re_flag[i][j] = false;
        }
        disRes[i] = 0;
    }
}

//spfa算法
void spfa(int mat[][maxN], bool flag[][maxN])
{

    for (int i = 1; i <= n; ++ i)
    {
        vis[i] = false;
        dis[i] = inf;
        //disRes[i] = 0;
    }
    int head = 0,tail = 1;
    dis[x] = 0;
    queue[0] = x;
    while (head < tail)
    {
        int u = queue[head];
        vis[u] = true;
        for (int i = 1; i <= n; ++ i)
        {
            if (flag[u][i] && dis[i] > dis[u] + mat[u][i])
            {
                dis[i] = dis[u] + mat[u][i];
                if (!vis[i])
                {
                    vis[i] = true;
                    queue[tail] = i;
                    tail ++;
                }
            }
        }
        vis[u] = false;
        head ++;
    }
    for (int i = 1; i <= n; ++ i)
    {
        disRes[i] += dis[i];
    }
}   www.zzzyk.com

int main()
{
    while (scanf("%d%d%d", &n, &m, &x) != EOF)
    {   int a, b, c;
        int mMax = -1;
        Init();
        for (int i = 0; i < m; ++ i)
        {
            scanf("%d%d%d", &a, &b, &c);
            mat[a][b] = c;
            flag[a][b] = true;
            re_mat[b][a] = c;
            re_flag[b][a] = true;
        }
        spfa(mat, flag);
        spfa(re_mat, re_flag);
        for (int i = 1; i <= n; ++ i)
        {
            if (mMax < disRes[i])
            {
                mMax = disRes[i];
            }
        }
        printf("%d\n", mMax);
    }
    return 0;
}
作者;zhang20072844

补充：软件开发 , C++ ,