题目传送门

大一做的最短路模板题,很适合练手 我分别利用了 3 种数据结构+Dijkstra/Floyd 来解决,解题步骤具体如下:

邻接矩阵

15ms

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e2+5;
const int INF = 0x3f3f3f3f;
int Map[maxn][maxn];
bool Vis[maxn];
int Dis[maxn];
int N,M,S,D;
inline void Init(){
memset(Map,INF,sizeof(Map));
memset(Vis,false,sizeof(Vis));
memset(Dis,0,sizeof(Dis));
int x,y,z;
while(M--){
scanf("%d%d%d",&x,&y,&z);
Map[x][y]=Map[y][x]=min(Map[x][y],z);
}
scanf("%d%d",&S,&D);
for(int i=0;i<N;++i){
Dis[i]=Map[S][i];
}
Dis[S]=0;
Vis[S]=true;
}
inline void Dijkstra(){
for(int l=0;l<N;++l){
int Min=INF,k;
for(int i=0;i<N;++i){
if(!Vis[i]&&Dis[i]<Min){
Min=Dis[i];
k=i;
}
}
Vis[k]=true;
if(Min!=INF){
for(int j=0;j<N;++j){
if(!Vis[j]&&Dis[j]>Dis[k]+Map[k][j]){
Dis[j]=Dis[k]+Map[k][j];
}
}
}
}
Dis[D]==INF?printf("-1n"):printf("%dn",Dis[D]);
}
int main(){
while(~scanf("%d%d",&N,&M)){
Init();
Dijkstra();
}
return 0;
}

邻接表

15ms

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
const int INF = 0x3f3f3f3f;
struct Node{
int from,to,cost;
Node(int a,int b,int c):from(a),to(b),cost(c){}
};
vector<Node>Edges;
vector<int>G[maxn];
int Dis[maxn];
int N,M,S,T;
typedef pair<int,int> Pair;
priority_queue<Pair,vector<Pair>,greater<Pair> >Q;
inline void AddEdge(int x,int y,int z){
Edges.push_back(Node(x,y,z));
G[x].push_back(Edges.size()-1);
}
inline void Init(){
Edges.clear();
memset(Dis,INF,sizeof(Dis));
for(int i=0;i<N;G[i++].clear());
int x,y,z;
while(M--){
scanf("%d%d%d",&x,&y,&z);
AddEdge(x,y,z);
AddEdge(y,x,z);
}
scanf("%d%d",&S,&T);
Dis[S]=0;
Q.push(Pair(0,S));
}
inline void Dijkstra(){
int Now,Val,L;
while(!Q.empty()){
Now=Q.top().second;
Val=Q.top().first;
Q.pop();
if(Dis[Now]<Val){continue;}
L=G[Now].size();
for(int i=0;i<L;++i){
if(Dis[Edges[G[Now][i]].to]>Dis[Now]+Edges[G[Now][i]].cost){
Dis[Edges[G[Now][i]].to]=Dis[Now]+Edges[G[Now][i]].cost;
Q.push(Pair(Dis[Edges[G[Now][i]].to],Edges[G[Now][i]].to));
}
}
}
Dis[T]==INF?printf("-1n"):printf("%dn",Dis[T]);
}
int main(){
while(~scanf("%d%d",&N,&M)){
Init();
Dijkstra();
}
return 0;
}

链式向前星

0ms

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2017;
const int INF = 0x3f3f3f3f;
struct Node{
int End;
int Value;
int Front;
Node(){}
Node(int a,int b,int c):End(a),Front(b),Value(c){}
}Edge[maxn];
int Head[maxn];
int Dis[maxn];
int N,M,S,D,Idx;
typedef pair<int,int>Pair;
priority_queue<Pair,vector<Pair>,greater<Pair> >Q;
inline void AddEdge(int S,int D,int V){
Edge[Idx]=Node(D,Head[S],V);
Head[S]=Idx++;
}
inline void Init(){
Idx=0;
memset(Head,-1,sizeof(Head));
memset(Dis,INF,sizeof(Dis));
int x,y,z;
while(M--){
scanf("%d%d%d",&x,&y,&z);
AddEdge(x,y,z);
AddEdge(y,x,z);
}
scanf("%d%d",&S,&D);
Pair pNew;
Dis[S]=0;
pNew.first=0;
pNew.second=S;
Q.push(pNew);
}
inline void Dijkstra(){
int Now,Val;
while(!Q.empty()){
Now=Q.top().second;
Val=Q.top().first;
Q.pop();
if(Dis[Now]<Val)continue;
for(int i=Head[Now];~i;i=Edge[i].Front){
if(Dis[Edge[i].End]>Dis[Now]+Edge[i].Value){
Dis[Edge[i].End]=Dis[Now]+Edge[i].Value;
Q.push(Pair(Dis[Edge[i].End],Edge[i].End));
}
}
}
Dis[D]==INF?printf("-1n"):printf("%dn",Dis[D]);
}
int main(){
while(~scanf("%d%d",&N,&M)){
Init();
Dijkstra();
}

Floyd

62ms

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e2+5;
const int INF = 0x3f3f3f3f;
int Map[maxn][maxn];
int N,M,S,D;
inline void Init(){
int x,y,z;
memset(Map,INF,sizeof(Map));
for(int i=0;i<N;++i){
Map[i][i]=0;
}
while(M--){
scanf("%d%d%d",&x,&y,&z);
Map[x][y]=Map[y][x]=min(Map[x][y],z);
}
scanf("%d%d",&S,&D);
}
inline void Floyd(){
for(int k=0;k<N;++k){
for(int i=0;i<N;++i){
for(int j=0;j<N;++j){
Map[i][j]=min(Map[i][j],Map[i][k]+Map[k][j]);
}
}
}
Map[S][D]==INF?printf("-1\n"):printf("%d\n",Map[S][D]);
}
int main(){
while(~scanf("%d%d",&N,&M)){
Init();
Floyd();
}
return 0;
}

后记

自从退 acm,很多东西都在遗忘…