http://poj.org/problem?id=3259
题目大意:
一个农民有农场,上面有一些虫洞和路,走虫洞可以回到 T秒前,而路就和平常的一样啦,需要花费时间走过。问该农民可不可能从某个点出发后回到该点,并且于出发时间之前?
思路:
就是让我们判断存不存在一条总权值未负的回路。
你想想,如果我们一直走这个回路,就可以无限的回到过去。( (╯‵□′)╯︵┻━┻世上哪有时空隧道。想回到过去么?如果可以? 你会去做什么,挽回让自己后悔的事情? ,咳咳,继续题解。)
那就用SPFA呗,如果一个点入队次数超过n,那么就存在回路。(因为SPFA求最短路,如果存在环,那么会一直入队。。出。。,也就是说环的是没有最小值的,而正环只会走一次。)
SPFA常见的优化有SLF和LLL
SLF是指在入队时如果当前点的dist值小于队首, 则插入到队首, 否则插入到队尾。
未优化的版本:
157MS
#include<cstdio> #include<string> #include<queue> using namespace std; const int INF=9999999; const int MAXN=520; const int MAXM=5200; struct edge { int to; int val; int next; }e[MAXM]; int len,head[MAXN]; int dis[MAXN]; int n,m,w; bool SPFA() { for(int i=1;i<=n;i++) dis[i]=INF; bool vis[MAXN]={0}; int cnt[MAXN]={0}; int cur=1; queue<int> q; q.push(cur); vis[cur]=true; cnt[cur]=1; dis[cur]=0; while(!q.empty()) { cur=q.front(); q.pop(); vis[cur]=false; if(cnt[cur]>n) return true; for(int i=head[cur] ;i!=-1; i=e[i].next) { int id=e[i].to; if( dis[cur] + e[i].val < dis[ id ] ) { dis[ id ] = dis[cur] + e[ i ].val; if(!vis[id]) { cnt[id]++; vis[id]=true; q.push(id); } } } } return false; } void add(int from,int to,int val) { e[len].to=to; e[len].val=val; e[len].next= head[from]; head[from]=len++; } int main() { int T; scanf("%d",&T); while(T--) { memset(head,-1,sizeof(head)); len=0; scanf("%d%d%d",&n,&m,&w); for(int i=0;i<m;i++) { int from,to,val; scanf("%d%d%d",&from,&to,&val); add(from,to,val); add(to,from,val); //双向的 } for(int i=0;i<w;i++) { int from,to,val; scanf("%d%d%d",&from,&to,&val); add(from,to,-val); } if( SPFA()) puts("YES"); else puts("NO"); } return 0; }
采用优化的版本:
63MS
#include<cstdio> #include<string> #include<queue> using namespace std; const int INF=9999999; const int MAXN=520; const int MAXM=5200; struct edge { int to; int val; int next; }e[MAXM]; int len,head[MAXN]; int dis[MAXN]; int n,m,w; bool SPFA() { for(int i=1;i<=n;i++) dis[i]=INF; bool vis[MAXN]={0}; int cnt[MAXN]={0}; int cur=1; deque<int> q; q.push_back(cur); vis[cur]=true; cnt[cur]=1; dis[cur]=0; while(!q.empty()) { cur=q.front(); q.pop_front(); vis[cur]=false; if(cnt[cur]>n) return true; for(int i=head[cur] ;i!=-1; i=e[i].next) { int id=e[i].to; if( dis[cur] + e[i].val < dis[ id ] ) { dis[ id ] = dis[cur] + e[ i ].val; if(!vis[id]) { cnt[id]++; vis[id]=true; if(!q.empty() && dis[id] < dis[q.front()]) q.push_front(id); else q.push_back(id); } } } } return false; } void add(int from,int to,int val) { e[len].to=to; e[len].val=val; e[len].next= head[from]; head[from]=len++; } int main() { int T; scanf("%d",&T); while(T--) { memset(head,-1,sizeof(head)); len=0; scanf("%d%d%d",&n,&m,&w); for(int i=0;i<m;i++) { int from,to,val; scanf("%d%d%d",&from,&to,&val); add(from,to,val); add(to,from,val); //双向的 } for(int i=0;i<w;i++) { int from,to,val; scanf("%d%d%d",&from,&to,&val); add(from,to,-val); } if( SPFA()) puts("YES"); else puts("NO"); } return 0; }