spfa单源最短路

spfa算法与dijkstra算法类似，也是用于计算图中某一点到其他各点的最短路径，但dijkstra要求路径权值不能为负，而spfa只要求不存在负环。

算法流程

设图中共有n个点，s为源点，d[i]表示s到i的最短路径。

• 初始化d数组：d[i] = inf, d[s] = 0
• 队列置空
• 将源点s入队
• 循环：出队一个元素a，遍历a的邻接点b，尝试用s->a->b的路径去更新s->b的路径，如果更新成功且b不在队列中，则将b入队。
• d数组即为源点到各点的最短路径。

说明：

• 为方便判断某个点是否在队列中，用inq[]数组做标记，入队/出队时更新。
• 如果存在负环，循环会一直进行下去，将出现某些点入队次数超过n。

int n, m, s, x, y, z, inq[10005], d[10005];
vector<pair<int,int>> g[10005];
queue<int> q;
int main() {
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &x, &y, &z);
        g[x].push_back(make_pair(y, z));
    }
    for (int i = 1; i <= n; i++)
        d[i] = 1e9;
    d[s] = 0; inq[s] = 1; q.push(s);
    while (!q.empty()) {
        int a = q.front(); q.pop(); inq[a] = 0;
        for (auto i : g[a]) {
            if (d[i.first] > d[a] + i.second) {
                d[i.first] = d[a] + i.second;
                if (!inq[i.first]) {
                    inq[i.first] = 1;
                    q.push(i.first);
                }
            }
        }
    }
    for (int i = 1; i <= n; i++)
        printf("%d%c", d[i] == 1e9 ? INT_MAX : d[i],
            i == n ? '\n' : ' ');
    return 0;
}