1、朴素Dijkstra算法
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
int n, m;
int g[N][N];
int dist[N];
bool st[N];
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int i = 0;i < n - 1;i ++)
{
int t = -1;
for(int j = 1;j <= n;j ++)
{
if(!st[j] && (t == -1 || dist[j] < dist[t]))
t = j;
}
st[t] = true;
for(int j = 1;j <= n;j ++)
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
scanf("%d%d", &n, &m);
memset(g, 0x3f, sizeof g);
while(m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = min(g[a][b], c);
}
printf("%d\n", dijkstra());
return 0;
}
2、spfa
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100000 + 10, M = 100000 + 10;
// head 表示头结点的下标
// e[i] 表示节点i的值，即e[i]是点编号
// ne[i] 表示节点i的next指针是多少，指向下一个下标
// idx 存储当前已经用到了哪个点（下标）
// w[i] 表示i下标对应的值是w[i]，即可等价成到达该下标i的权值是w[i]，即边的长度
int n, m;
int h[N], w[M], e[M], ne[M], idx;
int dist[N];
bool st[N];//是否在队列中
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
int spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;//表示1点在队列中
while(q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for(int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if(dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if(!st[j]) {
q.push(j);
st[j] = true;
}
}
}
}
return dist[n];
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while(m --)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
int t = spfa();
if(t == 0x3f3f3f3f) puts("impossible");
else printf("%d\n", t);
return 0;
}
3、floyd
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 210, INF = 1e9;
int n, m, Q;
int d[N][N];
void floyd()
{
for(int k = 1;k <= n;k ++)
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= n;j ++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
int main()
{
scanf("%d%d%d", &n, &m, &Q);
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= n;j ++)
if(i == j) d[i][j] = 0;
else d[i][j] = INF;
while(m --)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
d[a][b] = min(d[a][b], c);
}
floyd();
while(Q --)
{
int a, b;
scanf("%d%d", &a, &b);
int t = d[a][b];
if (t > INF / 2) puts("impossible");
else printf("%d\n", t);
}
return 0;
}
4、prim
最小生成树稠密图，
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int n, m;
int g[N][N];
int dist[N];
bool st[N];
int prim()
{
memset(dist, INF, sizeof dist);
int res = 0;
for(int i = 0;i < n;i ++)
{
int t = -1;
for(int j = 1;j <= n;j ++)
{
if(!st[j] && (t == -1 || dist[j] < dist[t]))
t = j;
}
if(i != 0 && dist[t] == INF) return INF;
st[t] = true;
if(i != 0) res += dist[t];
for(int j = 1;j <= n;j ++)
dist[j] = min(dist[j], g[t][j]);
}
return res;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1;i <= n; i ++)
for(int j = 1;j <= n;j ++)
if(i == j) g[i][j] = 0;
else g[i][j] = INF;
while(m --)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = g[b][a] = min(g[a][b], c);
}
int t = prim();
if(t == INF) puts("impossible");
else printf("%d\n", t);
return 0;
}
5、Kruskal
最小生成树稀疏图，
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100000 + 10, M = 200000 + 10, INF = 0x3f3f3f3f;
int n, m;
int p[N];
struct Edge {
int a, b, w;
bool operator< (const Edge &t) const {
return w < t.w;
}
}edge[M];
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int kruskal()
{
sort(edge, edge + m);
for(int i = 1;i <= n;i ++) p[i] = i;
int res = 0, cnt = 0;
for(int i = 0;i < m;i ++)
{
int a = edge[i].a, b = edge[i].b, w = edge[i].w;
a = find(a), b = find(b);
if(a != b) {
p[a] = b;
res += w;
cnt ++;
}
}
if(cnt < n - 1) return INF;
return res;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 0;i < m;i ++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
edge[i] = {a, b, c};
}
int t = kruskal();
if (t == INF) puts("impossible");
else printf("%d\n", t);
return 0;
}
6、拓扑排序
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100000 + 10;
int n, m;
int h[N], e[N], ne[N], idx;
int d[N], qv[N], qidx;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
bool topsort()
{
queue<int> q;
for(int i = 1;i <= n;i ++)
if(d[i] == 0)
q.push(i);
while(q.size())
{
int t = q.front();
q.pop();
qv[qidx ++] = t;
for(int i = h[t];i != -1;i = ne[i])
{
int j = e[i];
d[j] --;
if(d[j] == 0) q.push(j);
}
}
return qidx == n;
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
for(int i = 0;i < m;i ++)
{
int a, b, c;
scanf("%d%d", &a, &b);
add(a, b);
d[b] ++;
}
if(!topsort()) puts("-1");
else {
for (int i = 0; i < n; i ++ ) printf("%d ", qv[i]);
puts("");
}
}
网友评论