【模板】链式前向星+spfa

洛谷传送门——分糖果

博客——链式前向星

团队中一道题，数据很大，只能用链式前向星存储，spfa求单源最短路。

可做模板。

#include <cstdio>

#include <queue>

#include <cstring>

#include <algorithm>

using namespace std;

int n, p, c, ans, cnt;

long long m;

struct node

{

    int to, next;

}edge[];

int dis[], head[], x, y;

bool vis[];

void spfa()

{

    int i, j;

    queue <int> q;

    memset(dis, 0x7f, sizeof(dis));

    dis[c] = ;

    vis[c] = ;

    q.push(c);

    while(!q.empty())

    {

        i = q.front();

        q.pop();

        vis[i] = ;

        for(j = head[i]; j >= ; j = edge[j].next)

         if(dis[edge[j].to] > dis[i] + )

         {

             dis[edge[j].to] = dis[i] + ;

             if(!vis[edge[j].to])

             {

                 q.push(edge[j].to);

                 vis[edge[j].to] = ;

             }

         }

    }

}

int main()

{

    int i, j;

    scanf("%d %d %d", &n, &p, &c);

    scanf("%d", &m);

    memset(head, -, sizeof(head));

    for(i = ; i <= p; i++)

    {

        scanf("%d %d", &x, &y);

        edge[cnt].to = y;

        edge[cnt].next = head[x];

        head[x] = cnt++;

        edge[cnt].to = x;

        edge[cnt].next = head[y];

        head[y] = cnt++;

    }

    spfa();

    for(i = ; i <= n; i++) ans = max(ans, dis[i]);

    printf("%lld", ans + m);

    return ;

}

复制代码