洛谷传送门——分糖果
博客——链式前向星
团队中一道题，数据很大，只能用链式前向星存储，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[5000001];int dis[5000001], head[500001], x, y;bool vis[5000001];void spfa(){int i, j;queue <int> q;memset(dis, 0x7f, sizeof(dis));dis[c] = 1;vis[c] = 1;q.push(c);while(!q.empty()){i = q.front();q.pop();vis[i] = 0;for(j = head[i]; j >= 0; j = edge[j].next)if(dis[edge[j].to] > dis[i] + 1){dis[edge[j].to] = dis[i] + 1;if(!vis[edge[j].to]){q.push(edge[j].to);vis[edge[j].to] = 1;}}}}int main(){int i, j;scanf("%d %d %d", &n, &p, &c);scanf("%d", &m);memset(head, -1, sizeof(head));for(i = 1; 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 = 1; i <= n; i++) ans = max(ans, dis[i]);printf("%lld", ans + m);return 0;}复制代码
View Code
