最短路径-白红宇

最短路径

阅读量：6883 次

发布时间：2019-06-27

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

继续屯代码

floyed

1 #include
     
       2 #include
      
        3 #include
       
         4 double map[101][101],x[101],y[101]; 5 int n,m,u,v; 6 double dis(int u,int v){ 7     return (sqrt((x[u]-x[v])*(x[u]-x[v])+(y[u]-y[v])*(y[u]-y[v]))); 8 } 9 10 11 int main(){12     scanf("%d",&n);13     for (int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]);14     scanf("%d",&m);15     for (int i=0;i<=n;i++) for (int j=0;j<=n;j++) map[i][j]=100000;16     for (int i=0;i

迪杰斯塔拉

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 const int MAXN=10000; 6 vector
        
          W[MAXN],E[MAXN]; 7 int dis[MAXN],ans=0,n,m,map[MAXN][MAXN]; 8 bool vis[MAXN]={
   0}; 9 void add(int u,int v,int w1){10     E[u].push_back(v);11     W[u].push_back(w1);12 }13 14 void dij(){15     memset(dis,127,sizeof(dis));16     dis[1]=0;17     for (int i=0;i

优先队列优化后

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 using namespace std; 7 const int MAXN=10000; 8 vector
          
            W[MAXN],E[MAXN]; 9 int dis[MAXN],ans=0,n,m,map[MAXN][MAXN];10 bool vis[MAXN]={ 0};11 struct dott{ int num,v;12 };13 void add(int u,int v,int w1){14 E[u].push_back(v);15 W[u].push_back(w1);16 }17 18 struct cmp{19 bool operator()(dott &a,dott&b){20 return a.v>b.v;21 }22 };23 24 dott made(int x,int y){25 dott mid;26 mid.num=x;27 mid.v=y;28 return mid;29 }30 31 void dij(){32 priority_queue
           
            
             ,cmp >q;33 memset(dis,127,sizeof(dis));34 dis[1]=0;35 q.push(made(1,0));36 while(!q.empty()){37 dott mid=q.top();38 q.pop();39 if (mid.v>dis[mid.num]) continue;40 int minn=mid.num;41 for (int j=0;j

SPFA

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 const int MAXN=100; 6 vector
        
          E[MAXN],V[MAXN]; 7 bool vis[MAXN]; 8 int s=1,u,v,w,n,m,dis[MAXN],b[MAXN*2]; 9 void add(int u,int v,int w){10     E[u].push_back(v);11     V[u].push_back(w);12 }13 14 void spfa(){15     int h=0,t=1;16     memset(dis,127,sizeof(dis));17     dis[s]=0;18     b[t]=s;19     while (h
         
          dis[now]+V[now][i]){26                 dis[mid]=dis[now]+V[now][i];27                 if (!vis[mid]){28                     t++;29                     b[t]=mid;30                     vis[t]=1;31                 }32             } 33         }34     }35 }36 37 int main(){38     scanf("%d%d",&n,&m);39     for (int i=0;i