poj1613Cave Raider（带限制的最短路+spfa)(二)

16
55
*

Source

代码：

#include
      
       
#include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #define INF 0x3f3f3f3f using namespace std; const int maxn=50+10; int dis[maxn]; int n,m,st,en; bool vis[maxn]; struct Edge { int to,time; vector
            
             door; }; vector
             
              vec[maxn]; void read_graph() { char s[100+10]; for(int i=0;i
              
               ='0'&&s[i]<='9') x=x*10+s[i]-'0'; else { now.door.push_back(x); x=0; } } now.door.push_back(x); now.door.push_back(INF); now.to=u; vec[v].push_back(now); now.to=v; vec[u].push_back(now); } } void Spfa() { queue
               
                Q; while(!Q.empty()) Q.pop(); memset(dis,0x3f,sizeof(dis)); memset(vis,false,sizeof(vis)); dis[st]=0; vis[st]=true; Q.push(st); while(!Q.empty()) { int temp=Q.front(); vis[temp]=false; Q.pop(); for(int i=0;i
                
                 time+real_time) { dis[next]=time+real_time; if(!vis[next]) { vis[next]=true; Q.push(next); } } break; } } } } if(dis[en]==INF) printf("*\n"); else printf("%d\n",dis[en]); } int main() { while(~scanf("%d",&n)) { if(n==0) return 0; read_graph(); Spfa(); } return 0; }