借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;
}
|