当前位置: 代码迷 >> 综合 >> 最短路模板[spfa][dijkstra+堆优化][floyd]
  详细解决方案

最短路模板[spfa][dijkstra+堆优化][floyd]

热度:83   发布时间:2023-11-18 06:32:05.0

借bzoj1624练了一下模板(虽然正解只是floyd)

spfa:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using  namespace  std;
const  int  INF=100001;
const  int  maxm=10001,maxn=101;
int  n,m,x,y,w;
long  long  ans=0;
int  a[maxm];
int  dist[maxn];
bool  vis[maxn];
struct  edge{
     int  to,w;
     edge( int  _to, int  _w){to=_to;w=_w;}
};
vector <edge> g[maxm];
void  spfa( int  x){
     queue< int > q;
     memset (dist,63, sizeof (dist));
     memset (vis, false , sizeof (vis));
     dist[x]=0;
     vis[x]=1;
     q.push(x);
     
     while (!q.empty()){
         int  u=q.front();
         q.pop();
         vis[u]=0;
         int  l=g[u].size();
         for ( int  i=0;i<l;i++){
             int  v=g[u][i].to;
             if (dist[v]>dist[u]+g[u][i].w){
                 dist[v]=dist[u]+g[u][i].w;
                 if (!vis[v]){
                     vis[v]=1;q.push(v);
                 }
             }
         }
     }
}
int  main(){
     freopen ( "data.in" , "r" ,stdin);
     freopen ( "text.out" , "w" ,stdout);
     //freopen("data.txt","r",stdin);
     scanf ( "%d%d" ,&n,&m);
     for ( int  i=1;i<=m;i++)  scanf ( "%d" ,&a[i]);
     for ( int  i=1;i<=n;i++)
         for ( int  j=1;j<=n;j++){
             scanf ( "%d" ,&w);
             if (i!=j) g[i].push_back(edge(j,w));
         }
     for ( int  i=1;i<m;i++){
         spfa(a[i]);
         ans+=dist[a[i+1]];
     }
     cout<<ans;
     return  0;
}

  

dijkstra+priority_queue:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using  namespace  std;
const  int  INF=100001;
const  int  maxm=10001,maxn=101;
int  n,m,x,y,w;
long  long  ans=0;
int  a[maxm];
int  dist[maxn];
struct  edge{
     int  to,w;
     edge( int  _to, int  _w){to=_to;w=_w;}
};
vector <edge> g[maxm];
typedef  pair< int , int > P;
void  dijkstra( int  x){
     priority_queue< P , vector <P> , greater<P> > q;
     memset (dist,63, sizeof (dist));
     dist[x]=0;
     q.push(P(0,x));
     
     while (!q.empty()){
         P u=q.top();
         int  x=u.second;
         q.pop();
         if (dist[x]<u.first)  continue ;
         int  l=g[x].size();
         for ( int  i=0;i<l;i++){
             int  v=g[x][i].to;
             if (dist[v]>dist[x]+g[x][i].w){
                 dist[v]=dist[x]+g[x][i].w;
                 q.push(P(dist[v],v));
             }
         }
     }
}
int  main(){
     freopen ( "danger.in" , "r" ,stdin);
     freopen ( "danger.out" , "w" ,stdout);
     //freopen("data.txt","r",stdin);
     scanf ( "%d%d" ,&n,&m);
     for ( int  i=1;i<=m;i++)  scanf ( "%d" ,&a[i]);
     for ( int  i=1;i<=n;i++)
         for ( int  j=1;j<=n;j++){
             scanf ( "%d" ,&w);
             if (i!=j) g[i].push_back(edge(j,w));
         }
     for ( int  i=1;i<m;i++){
         dijkstra(a[i]);
         ans+=dist[a[i+1]];
     }
     cout<<ans;
     return  0;
}

  
floyd:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<vector>
using  namespace  std;
int  n,m,i,j,k,ans,f[102][102],a[10002];
int  main(){
   cin>>n>>m;
   for (i=1;i<=m;i++) scanf ( "%d" ,&a[i]);
   for (i=1;i<=n;i++)
   for (j=1;j<=n;j++)
     scanf ( "%d" ,&f[i][j]);
   for (k=1;k<=n;k++)
   for (i=1;i<=n;i++)
   for (j=1;j<=n;j++)
     f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
   for (i=2;i<=m;i++)ans+=f[a[i-1]][a[i]];
   cout<<ans;
   return  0;
}