江苏网站建设找拉米拉,眼科医院网站优化服务商,网站建设与维护是做什么,海盐县建设门户网站目录 游戏
思路
代码
魔法
思路
代码
P1364 医院设置
思路
代码
P1144 最短路计数
思路
代码 游戏
I-游戏_河南萌新联赛2024第#xff08;三#xff09;场#xff1a;河南大学 (nowcoder.com) 思路
利用dijkstra去寻找起点到其余所有点的最短路径#xff0c;当…
目录 游戏
思路
代码
魔法
思路
代码
P1364 医院设置
思路
代码
P1144 最短路计数
思路
代码 游戏
I-游戏_河南萌新联赛2024第三场河南大学 (nowcoder.com) 思路
利用dijkstra去寻找起点到其余所有点的最短路径当同时不能到达钥匙所在的地点和终点时这个数据无解输出-1记录好第一次dijkstra到钥匙和终点的最短路后在可以到达钥匙的前提下找到钥匙所在节点到其他点的最短路。
答案去第一次就可以到没拿钥匙到终点和拿了钥匙到终点的最短路的最小值。
代码
#includebits/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_queuepairint,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_queuepairint,intQ;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]在xy这个位置拥有h的血量时最少需要用多少次魔法。
代码
#includebits/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;vectorvectorvectorintdp(n 1, vectorvectorint(m 1, vectorint(h 1, inf)));for (int i 1; i n; i){for (int j 1; j m; j){cin mp[i][j];}}queuenodeq;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) 思路
数据不大我们暴力枚举每个点建医院时到其余点的最短路径这是最短路加上人数就是这个点的答案遍历完更新最小值即可。
代码
#includebits/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;
vectorvectorintf;
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){sumdis[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;
}
代码
#includebits/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;
vectorvectorintf;
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);}vectorintdis(n 1, inf);dis[1] 0;vectorboolvis(n 1, false);vectorintans(n 1);ans[1] 1;vis[1] true;queueintq;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;
}
