朴素版dijkstra $O(n ^ 2)$
1.最短路
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m;
int dist[N];
int g[N][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[t] > dist[j]))
t = j;
for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]);
st[t] = true;
}
return dist[n];
}
int main()
{
while (~scanf("%d%d", &n, &m), n, m)
{
memset(st, false, sizeof st);
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);
g[b][a] = min(g[b][a], c);
}
printf("%d\n", dijkstra());
}
return 0;
}
2.Til the Cows Come Home
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int dist[N];
int g[N][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[t] > dist[j]))
t = j;
for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]);
st[t] = true;
}
return dist[n];
}
int main()
{
scanf("%d%d", &m, &n);
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);
g[b][a] = min(g[b][a], c);
}
printf("%d\n", dijkstra());
return 0;
}
3.HDU Today
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <string>
using namespace std;
const int N = 160;
int n, cnt;
int g[N][N];
int dist[N];
bool st[N];
map<string, int> mp;
int dijkstra(int n)
{
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[t] > dist[j]))
t = j;
for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]);
st[t] = true;
}
if (dist[2] == 0x3f3f3f3f) return -1;
return dist[2];
}
int main()
{
while (~scanf("%d", &n) && n != -1)
{
memset(st, false, sizeof st);
mp.clear();
string start, end;
cin >> start >> end;
mp[start] = 1;
mp[end] = 2;
int cnt = 3;
memset(g, 0x3f, sizeof g);
while (n -- )
{
string a, b;
int c;
cin >> a >> b >> c;
if (!mp.count(a)) mp[a] = cnt ++ ;
if (!mp.count(b)) mp[b] = cnt ++ ;
g[mp[a]][mp[b]] = min(g[mp[a]][mp[b]], c);
g[mp[b]][mp[a]] = min(g[mp[b]][mp[a]], c);
}
if (start == end)
{
printf("0\n");
continue;
}
else printf("%d\n", dijkstra(cnt));
}
return 0;
}
4.最短路径问题
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1010;
int n, m;
int start, ed;
int dg[N][N], cg[N][N];
int dist[N], cost[N];
bool st[N];
void dijkstra()
{
for (int i = 1; i <= n; i ++ )
{
dist[i] = dg[start][i];
cost[i] = cg[start][i];
}
st[start] = true;
for (int i = 0; i < n - 1; i ++ )
{
int t = -1;
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
for (int j = 1; j <= n; j ++ )
if (dist[j] > dist[t] + dg[t][j])
{
dist[j] = dist[t] + dg[t][j];
cost[j] = cost[t] + cg[t][j];
}
else if (dist[j] == dist[t] + dg[t][j])
{
if (cost[j] > cost[t] + cg[t][j])
cost[j] = cost[t] + cg[t][j];
}
st[t] = true;
}
cout << dist[ed] << ' ' << cost[ed] << endl;
}
int main()
{
while (~scanf("%d%d", &n, &m), n, m)
{
memset(st, false, sizeof st);
memset(dg, 0x3f, sizeof dg);
memset(cg, 0x3f, sizeof cg);
while (m -- )
{
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
if (c < dg[a][b])
{
dg[a][b] = dg[b][a] = c;
cg[a][b] = cg[b][a] = d;
}
else if (c == dg[a][b])
cg[a][b] = cg[b][a] = min(cg[a][b], d);
}
scanf("%d%d", &start, &ed);
dijkstra();
}
return 0;
}
5.畅通工程续
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 210;
int n, m;
int start, ed;
int dist[N];
int g[N][N];
bool st[N];
int dijkstra()
{
for (int i = 0; i <= n - 1; i ++ )
dist[i] = g[start][i];
st[start] = true;
for (int i = 0; i < n - 1; i ++ )
{
int t = -1;
for (int j = 0; j < n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
for (int j = 0; j < n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]);
st[t] = true;
}
if (dist[ed] == 0x3f3f3f3f) return -1;
return dist[ed];
}
int main()
{
while (~scanf("%d%d", &n, &m))
{
memset(st, 0, sizeof st);
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
if (i == j)
g[i][j] = 0;
else
g[i][j] = g[j][i] = 0x3f3f3f3f;
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[b][a] = g[a][b] = min(g[a][b], c);
}
scanf("%d%d", &start, &ed);
printf("%d\n", dijkstra());
}
return 0;
}
6.Choose the best route
这道题一看就是多源汇最短路，但是这道题用floyd会超时。
但是这道题是终点已知，起点有多个。于是我们想到可以由终点找起点，所以可用dijkstra，注意题目上给的是有向图，所以存矩阵的时候要反向建图。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m, s, w;
int g[N][N];
int dist[N];
bool st[N];
void dijkstra(int s)
{
for (int i = 1; i <= n; i ++ )
dist[i] = g[s][i];
st[s] = 1;
for (int i = 0; i < n - 1; i ++ )
{
int t = -1;
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]);
st[t] = true;
}
}
int main()
{
while (~scanf("%d%d%d", &n, &m, &s))
{
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] = g[j][i] = 0x3f3f3f3f;
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[b][a] = min(g[b][a], c);
}
memset(st, 0, sizeof st);
dijkstra(s);
int res = 0x3f3f3f3f;
scanf("%d", &w);
while (w -- )
{
int x;
cin >> x;
res = min(res, dist[x]);
}
if (res == 0x3f3f3f3f) cout << "-1" << endl;
else cout << res << endl;
}
return 0;
}
7.A Walk Through the Forest
看题意看了半天才看懂，其实就是给你一个图，在这个图中，有这样一种路，假如你要从A走到B，那么B到终点的距离必须小于
A到终点的最短距离，问你这样的道路有多少。
1.直接dijkstra处理出每个点到2的最短距离，为dist[i];
2.DFS搜索每一条满足条件的道路（假设搜索的路是st->i那么st到i一定走得通并且dist[st]>dist[i];
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int g[N][N];
int dist[N];
bool st[N];
int p[N];
void dijkstra() // 以终点为起点遍历
{
for (int i = 1; i <= n; i ++ )
dist[i] = g[2][i];
st[2] = 1;
for (int i = 0; i < n - 1; i ++ )
{
int t = -1;
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]);
st[t] = true;
}
}
int dfs(int idx) // 记忆化搜素
{
if (p[idx]) return p[idx]; // 若该点已经搜索过，则直接返回
if (idx == 2) return 1;
for (int i = 1; i <= n; i ++ )
if (dist[i] < dist[idx] && g[i][idx] < 0x3f3f3f3f) // 满足条件且可走则条数累加
p[idx] += dfs(i);
return p[idx];
}
int main()
{
while (~scanf("%d", &n), n)
{
scanf("%d", &m);
memset(st, 0, sizeof st);
memset(p, 0, sizeof p);
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] = 0x3f3f3f3f;
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = g[b][a] = c;
}
dijkstra();
dfs(1);
cout << p[1] << endl;
}
return 0;
}
堆优化版dijkstra $O(mlogn)$
floyd $O(n ^ 3)$
1.一个人的旅行
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, t;
int s, d;
int g[N][N];
int start[N], ed[N];
int floyd()
{
int res = 0x3f3f3f3f;
for (int k = 1; k <= N; k ++ )
for (int i = 1; i <= N; i ++ )
if (g[i][k] != 0x3f3f3f3f)
for (int j = 1; j <= N; j ++ )
{
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
if (start[i] && ed[j] && res > g[i][j])
res = g[i][j];
}
return res;
}
int main()
{
while (~scanf("%d%d%d", &t, &s, &d))
{
for (int i = 0; i < N; i ++ )
for (int j = 0; j < N; j ++ )
if (i == j)
g[i][j] = 0;
else
g[i][j] = g[j][i] = 0x3f3f3f3f;
while (t -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = g[b][a] = min(g[a][b], c);
}
memset(start, 0, sizeof start);
memset(ed, 0, sizeof ed);
while (s -- )
{
int x;
cin >> x;
start[x] = 1;
}
while (d -- )
{
int y;
cin >> y;
ed[y] = 1;
}
printf("%d\n", floyd());
}
return 0;
}
等我 期末考完 干翻这套题单
好呀，加油！