poj-3259
题目
While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ’s farms comprises N (1 ≤ N ≤ 500) fields conveniently numbered 1..N, M (1 ≤ M ≤ 2500) paths, and W (1 ≤ W ≤ 200) wormholes.
As FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel through some paths and wormholes, and return to the starting field a time before his initial departure. Perhaps he will be able to meet himself :) .
To help FJ find out whether this is possible or not, he will supply you with complete maps to F (1 ≤ F ≤ 5) of his farms. No paths will take longer than 10,000 seconds to travel and no wormhole can bring FJ back in time by more than 10,000 seconds.
Input
Line 1: A single integer, F. F farm descriptions follow.
Line 1 of each farm: Three space-separated integers respectively: N, M, and W
Lines 2.. M+1 of each farm: Three space-separated numbers ( S, E, T) that describe, respectively: a bidirectional path between S and E that requires T seconds to traverse. Two fields might be connected by more than one path.
Lines M+2.. M+ W+1 of each farm: Three space-separated numbers ( S, E, T) that describe, respectively: A one way path from S to E that also moves the traveler back T seconds.
Output
Lines 1.. F: For each farm, output “YES” if FJ can achieve his goal, otherwise output “NO” (do not include the quotes).
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.
大意：就是有一个人有n个农场，农场与农场间共有M条路，长度为val，有的有虫洞，从虫洞过去后会回到val时间前，问你是否看到他自己
最短路，判负环，不用多说spfa
SPFA 判负环
bfs：判断入队次数是否超过顶点数
dfs： 判断是否重复递归
邻接矩阵
BFS 和SLF优化
SLF 优化：就是把队列改成双端队列，再入队前先判断，如果队首大于就放到队尾，小于的话放到队前。。。。。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<deque>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
int map[502][502];
int n,m,b;
void spfa()
{ int a[502]={
0};int vis[520]={
0};int dis[520];memset(dis,INF,sizeof(dis));vis[1]=1;dis[1]=0;deque<int>q;q.push_front(1);while(!q.empty()){int now=q.front();q.pop_front();vis[now]=0;for(int i=1;i<=n;i++){ if(dis[i]>dis[now]+map[now][i]){dis[i]=dis[now]+map[now][i];if(!vis[i]){ a[i]++;if(a[i]>=n) {printf("YES\n");return;}vis[i]=1;if(!q.empty()){if(dis[i]>dis[q.front()]){q.push_back(i); }elseq.push_front(i);}elseq.push_front(i);}}}}printf("NO\n");
}
int main()
{ std::ios::sync_with_stdio(false);int t;cin>>t;while(t--){ cin>>n>>m>>b;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j) map[i][j]=map[j][i]=0;else map[i][j]=map[j][i]=INF;}}for(int i=1;i<=m;i++){int x,y,v;cin>>x>>y>>v;if(map[x][y]>v)map[x][y]=map[y][x]=v;}for(int i=1;i<=b;i++){int x,y,v;cin>>x>>y>>v;if(map[x][y]>-v)map[x][y]=-v;}spfa();}return 0;
}DFS （超时，不知道是不是这道题的问题）
//poj 3259#include<iostream>
#include<cstring>
#include<cstdio>
#include<deque>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
int map[502][502];
int v[502]={
0};
int n,m,b;
int flag=0;
int d[502]={
0};
void spfa(int i)
{ if(flag) return; v[i]=1;for(int j=1;j<=n;j++){if(d[j]>d[i]+map[i][j]){d[j]=d[i]+map[i][j];if(v[j]){flag=1;return;}if(flag) return;spfa(j); }} v[i]=0;}
int main()
{ std::ios::sync_with_stdio(false);int t;cin>>t;while(t--){ cin>>n>>m>>b;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j) map[i][j]=map[j][i]=0;else map[i][j]=map[j][i]=INF;}}for(int i=1;i<=m;i++){int x,y,v;cin>>x>>y>>v;if(map[x][y]>v)map[x][y]=map[y][x]=v;}for(int i=1;i<=b;i++){int x,y,v;cin>>x>>y>>v;if(map[x][y]>-v)map[x][y]=-v;}memset(v,0,sizeof(v));memset(d,INF,sizeof(d));d[1]=0;flag=0;spfa(1);if(flag)cout<<"YES"<<endl;else{cout<<"NO"<<endl;}}return 0;
}邻接表
BFS
#include<cstring>
#include<cstdio>
#include<queue>
#define INF 0x3f3f3f3f
int m,n,w;
using namespace std;
int head[522];
int u; int dis[520];
struct sp
{int v,va,next;
}q[5200];
bool spfa()
{memset(dis,INF,sizeof(dis));bool vis[520]={0};int cur;int cnt[520]={0};vis[1]=true;dis[1]=0;cnt[1]=1;queue<int>p;p.push(1);while(!p.empty()){cur=p.front();p.pop();vis[cur]=false;for(int i=head[cur];i!=-1;i=q[i].next){int id=q[i].v;if(dis[cur]+q[i].va<dis[id]){dis[id]=dis[cur]+q[i].va;if(!vis[id]){cnt[id]++;vis[id]=true;p.push(id);if(cnt[id]>n){return true;}}}}}return false;}void add(int x,int y,int z)
{q[u].v=y;q[u].va=z;q[u].next=head[x];head[x]=u++;}
int main()
{int t;scanf("%d",&t);while(t--){ u=0;memset(head,-1,sizeof(head));scanf("%d%d%d",&m,&n,&w);for(int j=0;j<n;j++){int x,y,z;scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z);}for(int i=0;i<w;i++){int a,b,va;scanf("%d%d%d",&a,&b,&va); add(a,b,-va); } if(spfa()){ printf("YES\n");}elseprintf("NO\n");}return 0;
}dfs
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,w,o;
#define INF 0x3f3f3f3f
struct pp
{int v,va,next;
}ss[5200];
int head[520];
int vis[520];
int dis[520];
void add(int u,int v,int val)
{ss[o].v=v;ss[o].va=val;ss[o].next=head[u];head[u]=o++;
}
int flag=0;
void spfa(int x)
{ if(flag) return;vis[x]=1;for(int i=head[x];i!=-1;i=ss[i].next){ int v=ss[i].v;int val=ss[i].va;if(dis[v]>val+dis[x]){dis[v]=val+dis[x];if(vis[v]){flag=1;return;}spfa(v);if(flag) return;}}vis[x]=0;}
int main()
{int t;scanf("%d",&t);while(t--){ o=0;memset(head,-1,sizeof(head));scanf("%d%d%d",&n,&m,&w);for(int i=0;i<m;i++){int u,v,val;scanf("%d%d%d",&u,&v,&val);add(u,v,val);add(v,u,val); }for(int i=0;i<w;i++){int u,v,val;scanf("%d%d%d",&u,&v,&val);add(u,v,-val);} memset(dis,INF,sizeof(dis)); dis[1]=0;flag=0;memset(vis,0,sizeof(vis));spfa(1);if(flag)printf("YES\n");elseprintf("NO\n");}return 0;
}vector
和邻接表类似，只不过换用存法了
BFS
#include<cstring>
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#define INF 0x3f3f3f3f
int m,n,w;
using namespace std;
struct pp
{int v,va;
}ss;
vector<pp>qq[5200];
void spfa()
{int dis[520];memset(dis,INF,sizeof(dis)) ;int vis[520]={0};dis[1]=0;vis[1]=1;int cnt[520]={0};queue<int>q1;q1.push(1);cnt[1]=1;while(!q1.empty()){int now=q1.front();q1.pop();vis[now]=0;int len=qq[now].size();for(int i=0;i<len;i++){ int v=qq[now][i].v;int va=qq[now][i].va;if(dis[v]>va+dis[now]){ dis[v]=va+dis[now];if(!vis[v]){cnt[v]++;q1.push(v);vis[v]=1;if(cnt[v]>=m){printf("YES\n");return;}}}}}printf("NO\n");}
int main()
{int t;scanf("%d",&t);while(t--){scanf("%d%d%d",&m,&n,&w);for(int i=0;i<m+10;i++)qq[i].clear();for(int i=0;i<n;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);ss.v=y;ss.va=z;qq[x].push_back(ss);ss.v=x;qq[y].push_back(ss);}for(int j=0;j<w;j++){int x,y,z;scanf("%d%d%d",&x,&y,&z);ss.v=y;ss.va=-z;qq[x].push_back(ss);}spfa();} return 0;} DFS
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
int n,m,w,o;
#define INF 0x3f3f3f3f
struct pp
{int v,val;
}ss;
int flag=1;
int dis[520],vis[520];
vector<pp>q[520];
void spfa( int x)
{ if(flag) return;vis[x]=1;int len=q[x].size();for(int i=0;i<len;i++){ int v=q[x][i].v;int val=q[x][i].val;if(dis[v]>dis[x]+val){dis[v]=dis[x]+val;if(vis[v]){flag=1;return;}spfa(v);if(flag) return;}}vis[x]=0;
}int main()
{// ios::sync_with_stdio(false);int t;// cin>>t;scanf("%d",&t);while(t--){cin>>n>>m>>w;for(int i=1;i<=n;i++)q[i].clear();for(int i=0;i<m;i++){ int u,v;// cin>>u>>v>>ss.val;scanf("%d%d%d",&u,&v,&ss.val);ss.v=u;q[v].push_back(ss);ss.v=v;q[u].push_back(ss);}for(int i=0;i<w;i++){ int u,v,val;// cin>>u>>v>>val;scanf("%d%d%d",&u,&v,&val);ss.v=v;ss.val=-val;q[u].push_back(ss);}memset(vis,0,sizeof(vis));memset(dis,INF,sizeof(dis));dis[1]=0;flag=0;spfa(1);if(flag) printf("YES\n");else printf("NO\n");}return 0;
}vector真是个好东西！
还有这道题cin输出取消同步后比printf多300ms。
学习。。。。。