链式前向星+SPFA

今天听说vector不开o2是数组时间复杂度常数的1.5倍，瞬间吓傻。然后就问好的图表达方式，然后看到了链式前向星。于是就写了一段链式前向星+SPFA的，和普通的vector+SPFA的对拍了下，速度不错。

参考文章：http://malash.me/200910/linked-forward-star/

（百科 链式前向星 也有的）

适用于： 稠密图的表示

我们定义：

//MAXN表示最大节点数，MAXE表示最大边数

int head[MAXN],       //head[i]表示以i作为起点所对应边中的最后一条边的位置
v[MAXE],              //v[i]表示第i条边的终点
next[MAXE],        //next[i]表示边i之前的以同样起点的边的地址
w[MAXE];            //边的权值

实现：

#include <iostream>

#include <algorithm>

#include <queue>

#include <cstring>

using namespace std;

const int    MAXE = 10000,

             MAXN = 10000,

             INF  = 1000000000;

int e, n, a, b, c;

int head[MAXN],     //存起始位置

    v[MAXE],        //边的终点

    next[MAXE],     //下一条边地址

    w[MAXE],        //权值

    d[MAXN];

queue<int> q;

bool vis[MAXN];

void spfa(int root)

{

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

    for(int i = 1; i <= n; i++) d[i] = INF;

    d[root] = 0;

    q.push(root);

    int t, i;

    while(!q.empty())

    {

        t = q.front(); q.pop();

        i = head[t];

        while(i)

        {

            if(d[v[i]] > d[t]+w[i])

            {

                d[v[i]] = d[t] + w[i];

                if(!vis[v[i]])

                {

                    vis[v[i]] = 1;

                    q.push(v[i]);

                }

            }

            i = next[i];

        }

        vis[t] = 0;

    }

}

int main()

{

    cin >> n >> e;

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

    {

        cin >> b >> v[i] >> w[i];

        next[i] = head[b];    //指向同起点的上一条边

        head[b] = i;          //更新b指向的最后一条边位置

    }

    cin >> a;

    for(int i = 0; i < a; i++)

    {

        cin >> b >> c;

        spfa(b);

        if(d[c] == INF) cout << "No Answer!\n";

        else cout << d[c] << endl;

    }

    return 0;

}