当前位置：首页 > news >正文

工信部网站备案平台网络推广费用高吗

news 2026/4/7 14:42:36

工信部网站备案平台,网络推广费用高吗,网站页面设计培训,企业管理毕业论文题目分析但凡是最优方案可能需要访问同一个点的情况，都需要应用“拆点”，或者说分层图的技巧。多出来的维度主要是区分同一个点的不同状态而用。对于本题，访问的时机便是一个区分点。对于类似题“AB路线”，同一个K段的位置是…

题目

分析

但凡是最优方案可能需要访问同一个点的情况，都需要应用“拆点”，或者说分层图的技巧。多出来的维度主要是区分同一个点的不同状态而用。

对于本题，访问的时机便是一个区分点。

对于类似题“AB路线”，同一个K段的位置是一个区分点（不会跨越一个K段，不然不是最优）。

代码

#include <bits/stdc++.h>
using namespace std;const int N = 110;
const int M = 310;int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};struct node
{int x, y, t;
};int l[N][N], r[N][N];
int dist[N][N][M];
bool st[N][N];
int n, m, t;int bfs()
{memset(dist, 0x3f, sizeof dist);queue<node> q;q.push({1, 1, 0});dist[1][1][0] = 0;while(q.size()){auto u = q.front(); q.pop();for(int i = 0; i < 4; i++){int x = u.x + dx[i];int y = u.y + dy[i];if(x < 1 || y < 1 || x > n || y > m) continue;if(dist[x][y][u.t+1] > u.t + 1 && (u.t + 1 < l[x][y] || u.t + 1 > r[x][y])){if(x == n && y == m) return u.t + 1;dist[x][y][u.t+1] = u.t + 1;q.push({x, y, u.t+1});}}}return -1;
}int main()
{scanf("%d%d%d", &n, &m, &t);for(int i = 1; i <= t; i++){int x, y, a, b;scanf("%d%d%d%d", &x, &y, &a, &b);l[x][y] = a, r[x][y] = b;}printf("%d", bfs());
}