品牌营销和品牌推广,厦门网站优化推广,福州市建网站公司,企业网站源码系统题干#xff1a;
农夫约翰在探索他的许多农场#xff0c;发现了一些惊人的虫洞。虫洞是很奇特的#xff0c;因为它是一个单向通道#xff0c;可让你进入虫洞的前达到目的地#xff01;他的N#xff08;1≤N≤500#xff09;个农场被编号为1..N#xff0c;之间有M…题干
农夫约翰在探索他的许多农场发现了一些惊人的虫洞。虫洞是很奇特的因为它是一个单向通道可让你进入虫洞的前达到目的地他的N1≤N≤500个农场被编号为1..N之间有M1≤M≤2500条路径W1≤W≤200个虫洞。FJ作为一个狂热的时间旅行的爱好者他要做到以下几点开始在一个区域通过一些路径和虫洞旅行他要回到最开时出发的那个区域出发前的时间。也许他就能遇到自己了:)。为了帮助FJ找出这是否是可以或不可以他会为你提供F个农场的完整的映射到1≤F≤5。所有的路径所花时间都不大于10000秒所有的虫洞都不大于万秒的时间回溯。
Input
第1行一个整数F表示接下来会有F个农场说明。 每个农场第一行分别是三个空格隔开的整数NM和W 第2行到M1行三个空格分开的数字SET描述分别为需要T秒走过S和E之间的双向路径。两个区域可能由一个以上的路径来连接。 第M 2到M W1行三个空格分开的数字SET描述虫洞描述单向路径S到E且回溯T秒。
Output
F行每行代表一个农场 每个农场单独的一行” YES”表示能满足要求”NO”表示不能满足要求。
Sample Input
2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8
Sample Output
NO
YES
Hint
For farm 1, FJ cannot travel back in time. For farm 2, FJ could travel back in time by the cycle 1-2-3-1, arriving back at his starting location 1 second before he leaves. He could start from anywhere on the cycle to accomplish this. AC代码spfa邻接矩阵存图1079ms
#includecstdio
#includealgorithm
#includeiostream
#includequeue
#includecstdio
#includealgorithm
#includecstring
using namespace std;
int n;
const int MAX 505;
const int INF 0x3f3f3f3f;
int dis[MAX],maze[MAX][MAX],cnt[MAX];
bool vis[MAX];
bool spfa(int s){
// for(int i0; in; i) dis[i]99999999; //初始化每点i到s的距离dis[s]0; vis[s]1; //队列初始化,s为起点int i, v;queueint q;q.push(s);while (!q.empty()){ //队列非空vq.front(); //取队首元素q.pop();vis[v]0; //释放队首结点因为这节点可能下次用来松弛其它节点重新入队for(i1; in; i) //对所有顶点if (maze[v][i]!INF dis[i]dis[v]maze[v][i]){ dis[i] dis[v]maze[v][i]; //修改最短路if (vis[i]0){ //如果扩展结点i不在队列中入队cnt[i];vis[i]1;q.push(i);if(cnt[i] n) return true;}}}return false;
}void init() {memset(vis,0,sizeof(vis));memset(maze,INF,sizeof(maze));memset(dis,INF,sizeof(dis));memset(cnt,0,sizeof(cnt));
}
int main()
{int t;int M,W,u,v,w;cint; while(t--) {init();scanf(%d%d%d,n,M,W);for(int i 1; iM; i) {scanf(%d%d%d,u,v,w);if(wmaze[u][v])maze[u][v] maze[v][u] w;}for(int i 1; iW; i) {scanf(%d%d%d,u,v,w);maze[u][v] -w;}cnt[1] 1;if(spfa(1)) printf(YES\n);else printf(NO\n);}return 0 ;
}
AC代码2Bellman_Ford算法125ms
//Bellman_Ford算法试试
#includeiostream
#includealgorithm
#includecstdio
#includecstring
using namespace std;
#define MAXN 3000*2
#define INF 0xFFFFFFFint t , n , m, w;
int dis[MAXN];
struct Edge{int x;int y;int value;
}e[MAXN];bool judge(){for(int i 0 ; i m*2w ; i){if(dis[e[i].y] dis[e[i].x] e[i].value)return false;}return true;
}void Bellman_Ford(){dis[1] 0;for(int i 2 ; i n ; i)dis[i] INF;for(int i 1 ; i n ; i){for(int j 0 ; j m*2w; j){if(dis[e[j].y] dis[e[j].x] e[j].value)dis[e[j].y] dis[e[j].x] e[j].value;}}if(judge())printf(NO\n);elseprintf(YES\n);
}int main()
{int uu,vv,ww,i;scanf(%d,t);while(t--){scanf(%d%d%d,n,m,w);for(i0;im*2;){scanf(%d%d%d,uu,vv,ww);e[i].xuu;e[i].yvv;e[i].valueww;e[i].xvv;e[i].yuu;e[i].valueww;}for(;im*2w;i){scanf(%d%d%d,uu,vv,ww);e[i].xuu;e[i].yvv;e[i].value-ww;}Bellman_Ford();}return 0;
} AC代码3spfa邻接表储存图266ms
#includecstdio
#includealgorithm
#includeiostream
#includequeue
#includecstdio
#includealgorithm
#includecstring
using namespace std;
int n,cnt;
const int MAX 505;
const int INF 0x3f3f3f3f;
int dis[MAX],maze[MAX][MAX],cntt[MAX],head[MAX];
bool vis[MAX];
struct Edge {int to,w,ne;Edge(){}//没有此构造函数不能写 node t 这样Edge(int to,int w,int ne):to(to),w(w),ne(ne){}//可以写node(pos,cost)这样} e[200000 5];//数组别开小了
void add(int u,int v,int w) {e[cnt].to v;e[cnt].w w;e[cnt].ne head[u];head[u] cnt;
}bool spfa(int s){dis[s]0; vis[s]1; //队列初始化,s为起点int v;queueint q;q.push(s);while (!q.empty()){ //队列非空vq.front(); //取队首元素q.pop();vis[v]0; //释放队首结点因为这节点可能下次用来松弛其它节点重新入队for(int ihead[v]; i!-1; ie[i].ne) //对所有顶点{if (dis[e[i].to]dis[v]e[i].w) { dis[e[i].to] dis[v]e[i].w; //修改最短路if (vis[e[i].to]0) { //如果扩展结点i不在队列中入队cntt[e[i].to];vis[e[i].to]1;q.push(e[i].to);if(cntt[e[i].to] n) return true;}}}}return false;
}void init() {cnt 0;memset(vis,0,sizeof(vis));memset(maze,0,sizeof(maze));memset(e,0,sizeof(e));memset(dis,INF,sizeof(dis));memset(cntt,0,sizeof(cntt));memset(head,-1,sizeof(head));
}
int main()
{int t;int M,W,u,v,w;cint; while(t--) {init();scanf(%d%d%d,n,M,W);for(int i 1; iM; i) {scanf(%d%d%d,u,v,w);add(u,v,w);add(v,u,w);}for(int i 1; iW; i) {scanf(%d%d%d,u,v,w);add(u,v,-w);}cntt[1] 1;if(spfa(1)) printf(YES\n);else printf(NO\n);}return 0 ;
}AC代码4Bellmanford加优化47ms
//bellman算法
#include iostream
#include cstdio
#include cstring
#include algorithm
#define N 20100using namespace std;
const int INF 0x3f3f3f3f;
int n,m,mm;
int tot;
int dis[6005];
struct Edge {int u,v,w;
} e[6005];
void add(int u,int v,int w) {e[tot].u u;e[tot].v v;e[tot].w w;
}
bool bell() {memset(dis,INF,sizeof(dis));dis[1]0;int all n;int flag 0;while(all--) {flag 0;for(int i 1; itot; i) {if(dis[e[i].v] dis[e[i].u] e[i].w) {flag 1;dis[e[i].v] dis[e[i].u] e[i].w;}}if(flag 0) return false;}flag 0;for(int i 1; itot; i) {if(dis[e[i].v] dis[e[i].u] e[i].w) return 1;}return 0;
}int main()
{int f,a,b,c;cinf;while(f--) {tot 0;scanf(%d%d%d,n,m,mm);for(int i 1; im; i) {scanf(%d%d%d,a,b,c) ;add(a,b,c);add(b,a,c);}for(int i 1; imm; i) {scanf(%d%d%d,a,b,c);add(a,b,-c);}if(bell()) puts(YES);else puts(NO);}return 0 ;
}
//2
//3 3 1
//1 2 2
//1 3 4
//2 3 1
//3 1 3
