前向星表示法

2017-07-28 09:04:44

writer：pprp

前向星是一种星形表和司法，把所有的边集中在一起，形成一个边列表，比如第i条边(u,v) = w应当分别把起点、终点、权值存在三个数组中，但是下表相同

前向星是按照起始节点从小到大排序，除了你能直接用起点终点定位以外，前向星几乎是完美的。没有了用矩阵求图的对空间的浪费

题目：游戏厅

算法分析：前向星+bellman-ford算法

---

代码如下：

#include <iostream>

using namespace std;

const int maxn = 10001;
int x[maxn],y[maxn],e[maxn];
int d[maxn];
int n,m,s,t;
int change;

void init()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> x[i] >> y[i] >> e[i];
    }
    cin >> s >> t;
}

void bellman_ford(int s)
{
    for(int i =1; i<=n; i++)
        d[i] = INT_MAX;
    d[s] = 0;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(d[x[j]]!=INT_MAX&&d[y[j]] > d[x[j]]+e[j])
                d[y[j]] = d[x[j]]+e[j];
    if(d[t]!=INT_MAX)
        cout << d[t] << endl;
    else
        cout <<"No Solution!"<<endl;
}

int main()
{
    init();
    bellman_ford(s);
    return 0;
}