每日刷题（最短路、图论）

目录

游戏

思路

代码

魔法

思路

代码

P1364 医院设置

思路

代码

P1144 最短路计数

思路

代码

---

游戏

I-游戏_河南萌新联赛2024第（三）场：河南大学 (nowcoder.com)

思路

利用dijkstra去寻找起点到其余所有点的最短路径，当同时不能到达钥匙所在的地点和终点时，这个数据无解，输出-1，记录好第一次dijkstra到钥匙和终点的最短路后，在可以到达钥匙的前提下，找到钥匙所在节点到其他点的最短路。

答案去第一次就可以到没拿钥匙到终点和拿了钥匙到终点的最短路的最小值。

代码

#include<bits/stdc++.h>
#define int long long  
#define TEST int T; cin >> T; while (T--)
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
const int N = 1e6 + 30;
const int M = 1e3 + 10;
const int inf = 1000000000000000000;
using namespace std;int n, m, k;
struct node
{int u, v, w, d;
}e[N];
int head[N];
int dis[N], v2[N], v1[N];
int cnt = 0;
bool key = false;
void add(int x, int y, int z, int k)
{e[++cnt].w = z;e[cnt].d = k;e[cnt].u = y;e[cnt].v = head[x];head[x] = cnt;
}
priority_queue<pair<int,int> >q;
void solve() {cin >> n >> m >> k;for (int i = 1; i <= m; i++){int u, v, w, d;cin >> u >> v >> w >> d;add(u, v, w, d);add(v, u, w, d);}for (int i = 0; i <= n; i++) dis[i] = inf;dis[1] = 0;q.push({0,1});while (!q.empty()){auto t = q.top();int now = t.second;q.pop();if (v1[now]) continue;v1[now] = 1;for (int i = head[now]; i; i = e[i].v){int net = e[i].u;int pt = e[i].d;if (!key && pt == 0) continue;if (dis[net] > dis[now] + e[i].w){dis[net] = dis[now] + e[i].w;q.push({ -dis[net],net });}}}if (dis[n] >= inf && dis[k] >= inf){cout << "-1\n";return;}if (dis[k] >= inf){cout << dis[n] << "\n";}int ans1 = dis[n], ans2 = dis[k];key = true;for (int i = 0; i <= n; i++) dis[i] = inf;dis[k] = 0;priority_queue<pair<int,int>>Q;Q.push({0,k});while (!Q.empty()){auto t = Q.top();int now = t.second;Q.pop();if (v2[now]) continue;v2[now] = 1;for (int i = head[now]; i; i = e[i].v){int net = e[i].u;int pt = e[i].d;if (dis[net] > dis[now] + e[i].w){dis[net] = dis[now] + e[i].w;Q.push({-dis[net],net});}}}cout << min(ans1, ans2 + dis[n]) << "\n";
}
signed main() {ios;solve();return 0;
}

魔法

H-魔法_河南萌新联赛2024第（三）场：河南大学 (nowcoder.com)

思路

利用vector开一个三维数组去动态规划求解答案，因为只能向下走和向右走，所以只管走即可，不怕走到重复走过的点。

dp数组的含义是dp[x][y][h]，在（x，y）这个位置拥有h的血量时，最少需要用多少次魔法。

代码

#include<bits/stdc++.h>
#define int long long  
#define TEST int T; cin >> T; while (T--)
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
const int N = 1e6 + 30;
const int M = 1e3 + 10;
const int inf = 512785182741247112;
using namespace std;
int mp[3001][3001];
struct node
{int x, y, he, st;
};
void solve() {int n, m, h;cin >> n >> m >> h;vector<vector<vector<int>>>dp(n + 1, vector<vector<int>>(m + 1, vector<int>(h + 1, inf)));for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cin >> mp[i][j];}}queue<node>q;q.push({ 1, 1, h, 0 });dp[1][1][h] = 0;int dir[2][2] = { {1,0},{0,1} };while (q.size()){node it = q.front();q.pop();for (int i = 0; i < 2; i++){int tx = it.x + dir[i][0];int ty = it.y + dir[i][1];if (tx > n || ty > m) continue;int cost = mp[tx][ty];if (it.he > cost && dp[tx][ty][it.he - cost] > it.st){dp[tx][ty][it.he - cost] = it.st;q.push({ tx, ty, it.he - cost, it.st });}if (dp[tx][ty][it.he] > it.st + 1){dp[tx][ty][it.he] = it.st + 1;q.push({ tx, ty, it.he, it.st + 1 });}}}int ans = 1e9;for (int i = 1; i <= h; i++){ans = min(ans, dp[n][m][i]);}if (ans == 1e9) cout << "-1\n";else cout << ans << "\n";
}signed main() {solve();return 0;
}

P1364 医院设置

P1364 医院设置 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路

数据不大，我们暴力枚举每个点建医院时，到其余点的最短路径，这是最短路加上人数就是这个点的答案，遍历完更新最小值即可。

代码

#include<bits/stdc++.h>
#define int long long  
#define TEST int T; cin >> T; while (T--)
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
const int N = 1e6 + 30;
const int M = 1e3 + 10;
const int inf = 512785182741247112;
using namespace std;
int pe[200];
int n; 
vector<vector<int>>f;
int dis[101];
void bk()
{for (int i = 1; i <= n; i++) dis[i] = inf;
}
void dfs(int x, int fa)
{for (auto k : f[x]){if (k == fa) continue;if (dis[k] > dis[x] + 1){dis[k] = dis[x] + 1;dfs(k, x);}}
}
void solve() {cin >> n;f.resize(n + 2);for (int i = 1; i <= n; i++){cin >> pe[i];int x, y;cin >> x >> y;if (x != 0){f[i].push_back(x);f[x].push_back(i);}if (y != 0){f[i].push_back(y);f[y].push_back(i);}}int ans = 1e9;for (int i = 1; i <= n; i++){bk();dis[i] = 0;dfs(i, -1);int sum = 0;for (int i = 1; i <= n; i++){sum+=dis[i] * pe[i];}ans = min(ans, sum);}cout << ans << "\n";
}signed main() {ios;solve();return 0;
}

P1144 最短路计数

P1144 最短路计数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路

bfs+动态规划+SPFA求解，因为使用的是bfs遍历，每个点遍历到的第一次就可以得到最短路径，当我们第二次遍历到这个点时，如果最短路径相同，那么加上上一个节点的答案。

下面是主要代码

if (dis[k] > dis[x] + 1)
{dis[k] = dis[x] + 1;ans[k] = ans[x];if (!vis[k]){q.push(k);vis[k] = true;}
}
else if (dis[k] == dis[x] + 1)
{ans[k] += ans[x];ans[k] %= mod;
}

代码

#include<bits/stdc++.h>
#define int long long  
#define TEST int T; cin >> T; while (T--)
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
const int N = 1e6 + 30;
const int M = 1e3 + 10;
const int inf = 512785182741247112;
const int mod = 100003;
using namespace std;
int n, m;
vector<vector<int>>f;
void solve() {cin >> n >> m;f.resize(n + 1);int u, v;for (int i = 1; i <= m; i++){cin >> u >> v;if (u == v)continue;f[u].push_back(v);f[v].push_back(u);}vector<int>dis(n + 1, inf);dis[1] = 0;vector<bool>vis(n + 1, false);vector<int>ans(n + 1);ans[1] = 1;vis[1] = true;queue<int>q;q.push(1);while (q.size()){int x = q.front();q.pop();vis[x] = false;for (auto k : f[x]){if (dis[k] > dis[x] + 1){dis[k] = dis[x] + 1;ans[k] = ans[x];if (!vis[k]){q.push(k);vis[k] = true;}}else if (dis[k] == dis[x] + 1){ans[k] += ans[x];ans[k] %= mod;}}}for (int i = 1; i <= n; i++) cout << ans[i] << "\n";
}signed main() {solve();return 0;
}