1129. 热浪
题目大意：
给定若干个城镇和若干条双向路，从每条路走要有一定的花费，问从起点走到终点的最少花费是多少
思路：
spfa用队列
spfa：维持一个队列，队列中存放的是所有被更新过的点
每次从队列中取出最前面的点t，用这个点t更新它之后的所有点，即以t为头节点的邻接表的点
若能更新，即dist[j] > dist[t] + w[i]; 则更新，并且把被更新的点放入队列中。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 2510, M = 6200 * 2 + 10;
int n, m, s, t;
int h[N], e[M], ne[M], w[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 ++;
}
void spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[s] = 0;
queue<int> q;
q.push(s);
st[s] = true;
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;
}
}
}
}
}
int main()
{
cin >> n >> m >> s >>t;
memset(h, -1, sizeof h);
for(int i = 0; i < m; i ++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c), add(b, a, c);
}
spfa();
cout << dist[t] << endl;
return 0;
}
1128. 信使
题目大意：
从1号节点到其他所有节点的最短距离中最长的是多少？
思路：
求最长的最短路
单源最短路问题，但是可以用多源最短路问题的方法来做
Floyd算法比较简单
用Floyd求出1号节点到其他所有点的最短距离
代码：
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110, INF = 0x3f3f3f3f;
int n, m;
int d[N][N];
int main()
{
cin >> n >> m;
memset(d, 0x3f, sizeof d);
for (int i = 1; i <= n; i ++ ) d[i][i] = 0;
for (int i = 0; i < m; i ++ )
{
int a, b, c;
cin >> a >> b >> c;
d[a][b] = d[b][a] = min(d[a][b], c);
}
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 res = 0;
for (int i = 1; i <= n; i ++ )
if (d[1][i] == INF)
{
res = -1;
break;
}
else res = max(res, d[1][i]);
cout << res << endl;
return 0;
}
1127. 香甜的黄油
题目大意：
找到一个点，使得其他所有点到该点的距离之和最短
思路：
spfa能够求出某个点到其他所有点的距离最小值，所以，可以在spfa结束之后求出该点到其他所有点的距离之和
对每个点用一遍spfa，保留最小值即可
代码：
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 810, M = 3000, INF = 0x3f3f3f3f;
int n, p, m;
int id[N];
int h[N], e[M], w[M], ne[M], idx;
int dist[N], q[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(int start)
{
memset(dist, 0x3f, sizeof dist);
dist[start] = 0;
int hh = 0, tt = 1;
q[0] = start, st[start] = true;
while (hh != tt)
{
int t = q[hh ++ ];
if (hh == N) hh = 0;
st[t] = false;
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!st[j])
{
q[tt ++ ] = j;
if (tt == N) tt = 0;
st[j] = true;
}
}
}
}
int res = 0;
for (int i = 0; i < n; i ++ )
{
int j = id[i];
if (dist[j] == INF) return INF;
res += dist[j];
}
return res;
}
int main()
{
cin >> n >> p >> m;
for (int i = 0; i < n; i ++ ) cin >> id[i];
memset(h, -1, sizeof h);
for (int i = 0; i < m; i ++ )
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c), add(b, a, c);
}
int res = INF;
for (int i = 1; i <= p; i ++ ) res = min(res, spfa(i));
cout << res << endl;
return 0;
}
1126. 最小花费
题目大意：
n个人之间相互转账，人与人之间转账收的手续费各不相同（手续费是按转账的百分比计算），问A最少需要多少钱使得转账之后B能收到100元
思路：
求连乘的最大值等价于求连加的最大值（连乘取log就是连加）
可以用朴素dijkstra算法
dijkstra算法之后，dist[i]保留的是点i到指定起点的最值，可以指定最小或最大
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2010;
int n, m, S, T;
double g[N][N];
double dist[N];
bool st[N];
void dijkstra()
{
dist[S] = 1;
for (int i = 1; i <= n; i ++ )
{
int t = -1;
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] < dist[j]))
t = j;
st[t] = true;
for (int j = 1; j <= n; j ++ )
//指定保留最大值
dist[j] = max(dist[j], dist[t] * g[t][j]);
}
}
int main()
{
scanf("%d%d", &n, &m);
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
double z = (100.0 - c) / 100;
g[a][b] = g[b][a] = max(g[a][b], z);
}
cin >> S >> T;
dijkstra();
printf("%.8lf\n", 100 / dist[T]);
return 0;
}
920. 最优乘车
题目大意：
一条公交线路会经过若干个站点
现在一个人想从S站坐到T站，问最少进行几次换乘
算法：
难在建图：一条路线上任意两个点之间的距离看成1
因为两点之间的距离都是1， 所以直接用bfs即可找到最短路
只要一个点的距离被更新了，就把它放在队列里面
每次从队列中去除一个点，看能不能用这个点更新其他的点，能的话把被更新的点放在队列中，用它来更新其他的点
思路：
#include <cstring>
#include <iostream>
#include <algorithm>
#include <sstream>
using namespace std;
const int N = 510;
int m, n;
bool g[N][N];
int dist[N];
int stop[N];
int q[N];
void bfs()
{
int hh = 0, tt = 0;
memset(dist, 0x3f, sizeof dist);
q[0] = 1;
dist[1] = 0;
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = 1; i <= n; i ++ )
if (g[t][i] && dist[i] > dist[t] + 1)
{
dist[i] = dist[t] + 1;
q[ ++ tt] = i;
}
}
}
int main()
{
cin >> m >> n;
string line;
getline(cin, line);
while (m -- )
{
getline(cin, line);
stringstream ssin(line);
int cnt = 0, p;
while (ssin >> p) stop[cnt ++ ] = p;
for (int j = 0; j < cnt; j ++ )
for (int k = j + 1; k < cnt; k ++ )
g[stop[j]][stop[k]] = true;
}
bfs();
if (dist[n] == 0x3f3f3f3f) puts("NO");
else cout << max(dist[n] - 1, 0) << endl;
return 0;
}
1137. 选择最佳线路
题目大意：
张三和李四住在一个城市，给定多个单向公交线，每条线告诉从某个点到某个点所花费的时间，给定李四家附近的站点，已知张三家附近有多个公交站，都可以上车，问从张三家到李四家所花费的最短时间是多少
思路：
多个起点也可以当做单个起点，区别在于spfa开始时就把多个节点放入队列中，并设他们的dist都为0
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010, M = 20010, INF = 0x3f3f3f3f;
int n, m, T;
int h[N], e[M], w[M], ne[M], idx;
int dist[N], q[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 ++ ;
}
void spfa()
{
int scnt;
scanf("%d", &scnt);
memset(dist, 0x3f, sizeof dist);
int hh = 0, tt = 0;
while (scnt -- )
{
int u;
scanf("%d", &u);
dist[u] = 0;
q[tt ++ ] = u;
st[u] = true;
}
while (hh != tt)
{
int t = q[hh ++ ];
if (hh == N) hh = 0;
st[t] = false;
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!st[j])
{
q[tt ++ ] = j;
if (tt == N) tt = 0;
st[j] = true;
}
}
}
}
}
int main()
{
while (scanf("%d%d%d", &n, &m, &T) != -1)
{
memset(h, -1, sizeof h);
idx = 0;
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
spfa();
if (dist[T] == INF) dist[T] = -1;
printf("%d\n", dist[T]);
}
return 0;
}
1131. 拯救大兵瑞恩
#include <cstring>
#include <iostream>
#include <algorithm>
#include <deque>
#include <set>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 11, M = 360, P = 1 << 10;
int n, m, k, p;
int h[N * N], e[M], w[M], ne[M], idx;
int g[N][N], key[N * N];
int dist[N * N][P];
bool st[N * N][P];
set<PII> edges;
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void build()
{
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
for (int u = 0; u < 4; u ++ )
{
int x = i + dx[u], y = j + dy[u];
if (!x || x > n || !y || y > m) continue;
int a = g[i][j], b = g[x][y];
if (!edges.count({a, b})) add(a, b, 0);
}
}
int bfs()
{
memset(dist, 0x3f, sizeof dist);
dist[1][0] = 0;
deque<PII> q;
q.push_back({1, 0});
while (q.size())
{
PII t = q.front();
q.pop_front();
if (st[t.x][t.y]) continue;
st[t.x][t.y] = true;
if (t.x == n * m) return dist[t.x][t.y];
if (key[t.x])
{
int state = t.y | key[t.x];
if (dist[t.x][state] > dist[t.x][t.y])
{
dist[t.x][state] = dist[t.x][t.y];
q.push_front({t.x, state});
}
}
for (int i = h[t.x]; ~i; i = ne[i])
{
int j = e[i];
if (w[i] && !(t.y >> w[i] - 1 & 1)) continue; // 有门并且没有钥匙
if (dist[j][t.y] > dist[t.x][t.y] + 1)
{
dist[j][t.y] = dist[t.x][t.y] + 1;
q.push_back({j, t.y});
}
}
}
return -1;
}
int main()
{
cin >> n >> m >> p >> k;
for (int i = 1, t = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
g[i][j] = t ++ ;
memset(h, -1, sizeof h);
while (k -- )
{
int x1, y1, x2, y2, c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
int a = g[x1][y1], b = g[x2][y2];
edges.insert({a, b}), edges.insert({b, a});
if (c) add(a, b, c), add(b, a, c);
}
build();
int s;
cin >> s;
while (s -- )
{
int x, y, c;
cin >> x >> y >> c;
key[g[x][y]] |= 1 << c - 1;
}
cout << bfs() << endl;
return 0;
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1149440709@qq.com
