栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

zoj 2651 The Death Corrider

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

zoj 2651 The Death Corrider

#include <cstdio>#include <queue>#include <cstring>using namespace std;struct edge {int to;edge *next;} edg[100010], *vert[20010];const int inf = 1000000000;int n, a, b, deg[20010], dis[20010];bool flag[20010];inline void add_edge(int x, int y, int &top) {edge *p = &edg[++top];p->to = y;p->next = vert[x], vert[x] = p;}bool topsort() {queue <int> Q;for (int i = 0; i < n; i++) {if (deg[i] == 0) {Q.push(i);}}int cnt = 0;while (!Q.empty()) {int i = Q.front();Q.pop();++cnt;for (edge *p = vert[i]; p; p = p->next) {if (--deg[p->to] == 0) {Q.push(p->to);}}}return cnt == n;}void spfa() {queue <int> Q;for (int i = 0; i < n; i++) {dis[i] = 0;flag[i] = 1;Q.push(i);}while (!Q.empty()) {int i = Q.front();Q.pop();for (edge *p = vert[i]; p; p = p->next) {if (dis[p->to] > dis[i] - 1) {dis[p->to] = dis[i] - 1;if (!flag[p->to]) {flag[p->to] = 1;Q.push(p->to);}}}flag[i] = 0;}}int main() {while (scanf("%d%d%d", &n, &a, &b) != EOF) {if (!a || !b) {puts("No");continue;}int top = -1;memset(deg, 0, sizeof (deg));memset(vert, 0, sizeof (vert));++n;for (int i = 0; i < n; i++) {if (i + a < n) {add_edge(i, i + a, top);++deg[i + a];}if (i + b < n) {add_edge(i + b, i, top);++deg[i];}}if (!topsort()) {puts("No");continue;}else {spfa();puts("Yes");for (int i = 1; i < n; i++) {if (dis[i] == dis[i - 1]) {puts("Stay");}else if (dis[i] > dis[i - 1]) {printf("Right %dn", dis[i] - dis[i - 1]);}else {printf("Left %dn", dis[i - 1] - dis[i]);}}}}return 0;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/374081.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号