题目链接:点击打开链接
简单来说,就是从房间1走到n的可能性,如果可能,winnable,否则,hopeless。每到达一个房间可以得到,一个房间内的能量。能量小于等于0的时候,就是游戏结束的时候。
一个最短路的问题,思路很清晰并且真确的时候,就很简单了。
首先,说一下自己的想法为什么错误了。
这题的关键就是在于,如果存在正环,那么正环中的节点是否可以到达1点和n点。
那么,存在正环的话,不一定就一定能到达n点。为什么?因为,可能正环中的节点不一定能到达n点。
怎么样来判断,正环中的点是否能到达n点就成了该题目的关键点。
我一开始先到的是,bellman松弛一遍,然后再次松弛一遍,如果第二遍的dis[n]>第一遍的dis[n],那么就是可以到达。事实证明,这种想法是错误的。
为什么类?因为,如果第一次松弛不能到达n点的话,第二次松弛,还有可能不能到达n点。这样就会出现错误。
后来,找到别人的思路。
floyd先判断一下连通性,然后,再判断如果存在正环的话,正环中的节点是否和n点连通吗,若连通,一定能够到达。否则,不能。
代码:
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int N=103; const int M=10004; const int INF=-0xffffff; int dis[N],n,top,energy[N]; bool dp[N][N]; struct DoorWay{ int start,end; }way[M]; void floyd(){ for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) dp[i][j]=dp[i][j]||(dp[i][k]&&dp[k][j]); } } } void Bellman_ford(){ for(int i=1;i<=n;i++) dis[i]=INF; dis[1]=100; for(int i=1;i<n;i++){ for(int j=1;j<=top;j++){ int st=way[j].start; int en=way[j].end; if(dis[en]<dis[st]+energy[en]&&dis[st]+energy[en]>0) dis[en]=dis[st]+energy[en]; } } bool flag=false; for(int i=1;i<=top;i++){ int st=way[i].start; int en=way[i].end; if(dis[en]<dis[st]+energy[en]&&dis[st]+energy[en]>0&&dp[en][n]){ flag=true; printf("winnable\n"); break; } } if(!flag){ if(dis[n]>0) printf("winnable\n"); else printf("hopeless\n"); } } int main(){ while(scanf("%d",&n)&&(n!=-1)){ top=0; memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) dp[i][i]=true; for(int i=1;i<=n;i++){ int number,id; scanf("%d%d",&energy[i],&number); for(int j=1;j<=number;j++){ scanf("%d",&id); top++; dp[i][id]=true; way[top].start=i; way[top].end=id; } } floyd(); Bellman_ford(); } return 0; }
还是需要正确的想法。