poj2263 zoj1952 Heavy Cargo(floyd||spfa)-白红宇

poj2263 zoj1952 Heavy Cargo(floyd||spfa)

阅读量：4970 次

发布时间：2019-06-12

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

这道题数据范围小，方法比较多。我用floyd和spfa分别写了一下，spfa明显有时间优势。

一个小技巧在于：把城市名称对应到数字序号，处理是用数字。

方法一：spfa

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    using namespace std;#define pii pair
                    
                     #define LL long long intconst int eps=1e-8;const int INF=1000000000;const int maxn=200+10;int n,r,cas=0,ton,num,used[maxn],d[maxn],m[maxn][maxn];char city[maxn][33];char s[33],e[33];vector
                     
                      v[maxn];int index(char *ss){ int i; for(i=0;i

q; q.push(s); used[s]=1; while(!q.empty()) { int t=q.front(); used[t]=0; q.pop(); int siz=v[t].size(); for(int i=0;i

d[k]) { d[k]=min(d[t],m[t][k]); if(used[k]==0) {q.push(k);used[k]=1;} } } } return d[e];}int main(){ //freopen("in8.txt","r",stdin); //freopen("out.txt","w",stdout); while(scanf("%d%d",&n,&r)==2) { if(n==0&&r==0) break; printf("Scenario #%d\n",++cas); ini(); for(int i=0;i

spfa

方法二：floyd

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    using namespace std;#define pii pair
                    
                     #define LL long long intconst int eps=1e-8;const int INF=1000000000;const int maxn=200+10;int n,r,m[maxn][maxn],cas=0,ton,num;char city[maxn][33];char s[33],e[33];int index(char *ss){ int i; for(i=0;i

floyd

转载于:https://www.cnblogs.com/zywscq/p/4102787.html

你可能感兴趣的文章