- 科技
- 图论模板
单源最短路
朴素版Dijkstra
#include<iostream>
#include<cstring>
using namespace std
;
int g
[3000][3000];
bool used
[3000];
int d
[3000];
int n
,m
,a
,b
;
void dijkstra(int s
){
memset(d
,0x3f,sizeof d
);
memset(used
,0,sizeof used
);
d
[s
]=0;
for(int i
=1;i
<=n
;i
++){
int k
;
int mins
=0x3f3f3f3f;
for(int i
=1;i
<=n
;i
++){
if(!used
[i
]&&mins
>d
[i
]){
k
=i
;
mins
=d
[i
];
}
}
used
[k
]=true;
for(int i
=1;i
<=n
;i
++){
if(!used
[i
]&&d
[i
]>d
[k
]+g
[k
][i
]){
d
[i
]=d
[k
]+g
[k
][i
];
}
}
}
}
int main(){
cin
>> n
>> m
>> a
>> b
;
memset(g
,0x3f,sizeof g
);
for(int i
=0;i
<m
;i
++){
int x
,y
,w
;
cin
>> x
>> y
>> w
;
g
[x
][y
]=w
;
g
[y
][x
]=w
;
}
dijkstra(a
);
cout
<< d
[b
] << endl
;
return 0;
}
小顶堆优化Dijkstra
#include<iostream>
#include<cstring>
#include<queue>
using namespace std
;
int g
[3000][3000];
bool used
[3000];
int d
[3000];
int n
,m
,a
,b
;
void dijkstra(int s
){
priority_queue
<pair
<int,int>,vector
<pair
<int,int> >,greater
<pair
<int,int> > > pq
;
memset(d
,0x3f,sizeof d
);
pq
.push(make_pair(0,s
));
while(!pq
.empty()){
pair
<int,int> p
=pq
.top();
pq
.pop();
int v
=p
.second
;
if(d
[v
]<p
.first
)continue;
d
[v
]=p
.first
;
for(int i
=1;i
<=n
;i
++){
if(d
[i
]>d
[v
]+g
[v
][i
]){
d
[i
]=d
[v
]+g
[v
][i
];
pq
.push(make_pair(d
[i
],i
));
}
}
}
}
int main(){
cin
>> n
>> m
>> a
>> b
;
memset(g
,0x3f,sizeof g
);
for(int i
=0;i
<m
;i
++){
int x
,y
,w
;
cin
>> x
>> y
>> w
;
g
[x
][y
]=w
;
g
[y
][x
]=w
;
}
dijkstra(a
);
cout
<< d
[b
] << endl
;
return 0;
}
Floyd
多源最短路模板
#include<iostream>
#include<cstring>
#include<queue>
using namespace std
;
int g
[600][600];
int n
,a
;
void floyd(){
for(int k
=1;k
<=n
;k
++){
for(int i
=1;i
<=n
;i
++){
for(int j
=1;j
<=n
;j
++){
g
[i
][j
]=min(g
[i
][j
],g
[i
][k
]+g
[k
][j
]);
}
}
}
}
int main(){
cin
>> n
;
memset(g
,0x3f,sizeof g
);
for(int i
=1;i
<=n
;i
++){
for(int j
=1;j
<=n
;j
++){
cin
>> a
;
g
[i
][j
]=a
;
}
}
floyd();
for(int i
=1;i
<=n
;i
++){
for(int j
=1;j
<=n
;j
++){
cout
<< g
[i
][j
] << " ";
}
cout
<< endl
;
}
return 0;
}
路径还原
#include<iostream>
#include<cstring>
#include<stack>
using namespace std
;
int g
[3000][3000];
int used
[3000];
int d
[3000];
int pre
[3000];
int n
,m
,a
,b
;
void dijkstra(int s
){
memset(d
,0x3f,sizeof d
);
memset(used
,0,sizeof used
);
for(int i
=1;i
<=n
;i
++)pre
[i
]=i
;
d
[s
]=0;
for(int i
=1;i
<=n
;i
++){
int k
;
int mins
=0x3f3f3f3f;
for(int i
=1;i
<=n
;i
++){
if(!used
[i
]&&mins
>d
[i
]){
k
=i
;
mins
=d
[i
];
}
}
used
[k
]=true;
for(int i
=1;i
<=n
;i
++){
if(!used
[i
]&&d
[i
]>d
[k
]+g
[k
][i
]){
pre
[i
]=k
;
d
[i
]=d
[k
]+g
[k
][i
];
}
}
}
}
int main(){
cin
>> n
>> m
>> a
>> b
;
memset(g
,0x3f,sizeof g
);
for(int i
=0;i
<m
;i
++){
int x
,y
,w
;
cin
>> x
>> y
>> w
;
g
[x
][y
]=w
;
g
[y
][x
]=w
;
}
dijkstra(a
);
int i
=b
;
cout
<< d
[b
] << endl
;
stack
<int> sta
;
while(pre
[i
]!=i
){
sta
.push(i
);
i
=pre
[i
];
}
cout
<< a
<< " ";
while(!sta
.empty()){
cout
<< sta
.top() << " ";
sta
.pop();
}
return 0;
}
Prim()算法模板
#include<iostream>
#include<vector>
#include<cstring>
using namespace std
;
int n
,m
;
vector
<pair
<int,int> > vec
[2*100005];
bool used
[2*100005];
int d
[2*100005];
int x
,y
,z
;
long long prim(){
memset(d
,0x3f,sizeof d
);
memset(used
,0,sizeof used
);
d
[1]=0;
long long ans
=0;
for(int i
=1;i
<=n
-1;i
++){
int k
,mins
=0x3f3f3f3f,lens
=vec
[i
].size();
for(int j
=1;j
<=n
;j
++){
if(!used
[j
]&&mins
>d
[j
]){
mins
=d
[j
];
k
=j
;
}
}
used
[k
]=true;
ans
+=d
[k
];
for(int j
=0;j
<lens
;j
++){
pair
<int,int> P
=vec
[k
][j
];
if(!used
[P
.first
]){
d
[P
.first
]=min(d
[P
.first
],P
.second
);
}
}
}
return ans
;
}
int main(){
cin
>> n
>> m
;
for(int i
=1;i
<=m
;i
++){
cin
>> x
>> y
>> z
;
vec
[x
].push_back(make_pair(y
,z
));
vec
[y
].push_back(make_pair(x
,z
));
}
cout
<< prim() << endl
;
return 0;
}
Kruskal模板
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std
;
int n
,m
;
struct node
{
int x
,y
,cost
;
node(int a
,int b
,int c
):x(a
),y(b
),cost(c
){
}
node(){
}
bool operator < (const node
&y
)const{
return cost
<y
.cost
;
}
};
node edges
[5*100005];
int pre
[2*100005];
int rank
[2*100005];
void init(){
for(int i
=1;i
<=n
;i
++){
pre
[i
]=i
;
rank
[i
]=0;
}
}
int find(int x
){
if(pre
[x
]==x
)return x
;
return pre
[x
]=find(pre
[x
]);
}
void unite(int x
,int y
){
int p1
=find(x
);
int p2
=find(y
);
if(p1
==p2
)return;
if(rank
[p1
]<rank
[p2
]){
pre
[p1
]=p2
;
}
else{
pre
[p2
]=p1
;
if(rank
[p1
]==rank
[p2
]){
rank
[p1
]++;
}
}
}
bool same(int x
,int y
){
return find(x
)==find(y
);
}
long long Kruskal(){
init();
sort(edges
,edges
+m
);
long long ans
=0;
for(int i
=0;i
<m
;i
++){
node temp
=edges
[i
];
if(!same(temp
.x
,temp
.y
)){
unite(temp
.x
,temp
.y
);
ans
+=temp
.cost
;
}
}
return ans
;
}
int main(){
cin
>> n
>> m
;
int x
,y
,z
;
for(int i
=0;i
<m
;i
++){
cin
>> x
>> y
>> z
;
edges
[i
]=node(x
,y
,z
);
}
cout
<< Kruskal() << endl
;
return 0;
}
Processed:
0.018, SQL:
9
