今天听说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;
}
05-06 11:11