模版题,复习最短路模版用
哨兵送信的最短距离,取决于从起点到n个哨所的最长路径.求一遍最短路径后,选取最长的路径输出即可,如果有不能到达的则输出-1
通过最短路算法,枚举以每个牧场为中心,其他牧场的奶牛到该牧场到距离之和,取最小值,就可以得到本题的答案
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
constexpr int N = 5020;
int h[N], e[N], ne[N], w[N], idx;
int dist[N], n, p, t, cnt[N];
bool st[N];
typedef pair<int, int> PII;
inline void add(int a, int b, int c) {
e[++idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx;
}
inline int dijkstra(int s) {
for (int i = 0; i <= p; i++) { st[i] = 0, dist[i] = 10010; }
priority_queue<PII, vector<PII>, greater<PII>> q;
q.push({0, s});
dist[s] = 0;
while (q.size()) {
auto t = q.top(); q.pop();
int ver = t.second, d = t.first;
if (st[ver]) continue;
st[ver] = 1;
for (int i = h[ver]; i; i = ne[i]) {
int j = e[i];
if (dist[j] > d + w[i]) {
dist[j] = d + w[i];
if (!st[j]) q.push({dist[j], j});
}
}
}
int res = 0;
for (int i = 1; i <= p; i++) {
if (i == s) continue;
res += cnt[i] * dist[i];
}
return res;
}
int main() {
scanf("%d%d%d", &n, &p, &t);
for (int i = 1; i <= n; i++) {
int x; scanf("%d", &x);
cnt[x]++;
}
while (t --) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
int res = 0x3f3f3f3f;
for (int i = 1; i <= p; i++)
res = min(res, dijkstra(i));
printf("%d\n", res);
return 0;
}
本题是以浮点数为边权的最短路问题,每条边权的值为val/(1-1.0*w[i]/100),直接求最短路即可
本题给你若干条公交线路.
对于同一条线路上的站点,我们可以直接让前面的站点和后面的站点连一条边,这样一来,路径长度-1就代表需要换乘的最少次数
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <sstream>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
constexpr int N = 1010;
int h[N], e[N], ne[N], idx;
int dist[N], n, m;
bool st[N];
inline void add(int a, int b) {
e[++idx] = b, ne[idx] = h[a], h[a] = idx;
}
char s[N];
inline void build() {
stringstream stream;
stream << s;
int a[N], t = 0;
while (stream >> a[t]) t++;
for (int i = 0; i < t; i++)
for (int j = i + 1; j < t; j++)
add(a[i], a[j]);
}
inline int dijkstra() {
memset(dist, 0x3f, sizeof dist);
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1});
dist[1] = 0;
while (heap.size()) {
auto t = heap.top(); heap.pop();
int ver = t.second, distance = t.first;
if (st[ver]) continue;
st[ver] = 1;
for (int i = h[ver]; i; i = ne[i]) {
int j = e[i];
if (dist[j] > distance + 1) {
dist[j] = distance + 1;
if (!st[j]) heap.push({dist[j], j});
}
}
}
if (dist[m] == 0x3f3f3f3f) return -1;
return dist[m];
}
int main() {
scanf("%d%d", &n, &m); getchar();
for (int i = 0; i < n; i++) {
fgets(s, N, stdin);
build();
}
int t = dijkstra();
if (t != -1) printf("%d", t - 1);
else puts("NO");
return 0;
}
本题求以物易物的方式求换取物品1需要的最少花费,那么我们可以将直接购买的物品和优惠物品之间反向建边,这样问题就变成了终点为1,起点为所有物品,边权为价格的最短路问题.
本题有等级差的限制,但数据范围不是很大,可以枚举等级差的范围,取最小值
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
constexpr int N = 110, M = 100010, INF = 0x3f3f3f3f;
typedef pair<int, int> PII;
int h[N], e[M], ne[M], w[M], idx;
int n, m, g[N][N], level[N], dist[N];
bool st[N];
inline void add(int a, int b, int c) {
e[++idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx;
}
inline int dijkstra(int lower, int upper) {
priority_queue<PII, vector<PII>, greater<PII>> heap;
for (int i = 0; i <= n; i++) { st[i] = 0, dist[i] = INF; }
heap.push({0, 0});
dist[0] = 0;
while (heap.size()) {
auto t = heap.top(); heap.pop();
int ver = t.second, d = t.first;
if (st[ver]) continue;
st[ver] = 1;
for (int i = h[ver]; i; i = ne[i]) {
int j = e[i];
if (level[j] < lower or level[j] > upper) continue;
if (dist[j] > d + w[i]) {
dist[j] = d + w[i];
if (!st[j]) heap.push({dist[j], j});
}
}
}
return dist[1];
}
int main() {
scanf("%d%d", &m, &n);
for (int i = 1; i <= n; i++) {
static int p, t;
scanf("%d%d%d", &p, level + i, &t);
add(0, i, p);
while (t --) {
int a, b; scanf("%d%d", &a, &b);
add(a, i, b);
}
}
int res = INF;
for (int i = level[1] - m; i <= level[1]; i++) {
res = min(res, dijkstra(i, i + m));
}
printf("%d\n", res);
return 0;
}