HDU4522 湫湫系列故事——过年回家-白红宇

HDU4522 湫湫系列故事——过年回家

阅读量：5011 次

发布时间：2019-06-12

本文共 2043 字，大约阅读时间需要 6 分钟。

传送门：

中文题面。

思路：拿spfa对卧铺和硬铺分别跑spfa，然后找两个的最短路。体感堆优化的dij也可以，不过spfa跑跑就过去了。有个细节是最后得用long long 存数据，其他的没啥。

去重边是拿set存的邻接表。判断是否是数字用的isdigit函数。懒的要命系列。

#include 
     
        #include 
      
         #include 
       
          #include 
        
           #include 
         
            #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #include 
                
                  #include 
                  #include 
                  
                    #include 
                   
                     #include 
                    
                      using namespace std; #define LL long long #define pb push_back #define mk make_pair #define pill pair
                     
                       #define mst(a, b) memset(a, b, sizeof a) #define REP(i, x, n) for(int i = x; i <= n; ++i)int vis[1000],dis[1000],n,m;set
                      
                       v1[210];set
                       
                        v2[210];void spfa(int st,int key){ queue
                        
                         q; memset(vis,0,sizeof(vis)); for(int i = 0 ; i <= n ; i++){ dis[i] = 100000000; } q.push(st); vis[st] = 1; dis[st] = 0; while(!q.empty()){ int v = q.front(); vis[v] = 0 ; q.pop(); if(key == 1){ set
                         
                          ::iterator it = v1[v].begin(); for(;it != v1[v].end(); it++){ int to = *it; if(dis[to] > dis[v] + 1){ dis[to] = dis[v] + 1; if(!vis[to]){ q.push(to); vis[to] = 1; } } } } else{ set
                          
                           ::iterator it = v2[v].begin(); for(;it != v2[v].end(); it++){ int to = *it; if(dis[to] > dis[v] + 1){ dis[to] = dis[v] + 1; if(!vis[to]){ q.push(to); vis[to] = 1; } } } } }}int main(){ int t; for(scanf("%d",&t);t--;){ char s[10010]; scanf("%d %d",&n,&m); for(int i = 0 ; i <= n ; i++){ v1[i].clear(); v2[i].clear(); } while(m--){ int num; scanf("%s %d",s,&num); int k = 0, y = -1; int len = strlen(s); for(int i = 0 ; i < len ; i++){ if(isdigit(s[i])){ k = k * 10 + (s[i] - '0'); } else{ if(y == -1) y = k; else{ v1[y].insert(k); if(num > 0){ v2[y].insert(k); } y = k; } k = 0; } } v1[y].insert(k); if(num > 0){ v2[y].insert(k); } } long long ans1 = 0,ans2 = 0; int d1,d2,st,ed; scanf("%d %d %d %d",&d1,&d2,&st,&ed); spfa(st,1); ans1 = dis[ed]; spfa(st,0); ans2 = dis[ed]; if(ans1 == 100000000 && ans2 == 100000000 ){ puts("-1");continue; } //printf("%d %d\n",ans1,ans2); printf("%lld\n",min(ans1*d1*1LL,ans2*d2*1LL)); }}