网站开发学什么语音,关于对网站建设工作情况的通报,h5网站还有哪些,教务管理网站开发gym103117L. Spicy Restaurant
题意#xff1a;
有n个点#xff0c;m个边#xff0c;每个点都有一个能量值#xff0c;现在有q个人#xff0c;每个人有自己的能量值#xff0c;现在每个人都要去离自己最近且能量值小于等于自身的点。 1n,m1e5 1q5e5 1
有n个点m个边每个点都有一个能量值现在有q个人每个人有自己的能量值现在每个人都要去离自己最近且能量值小于等于自身的点。 1n,m1e5 1q5e5 1wi1001w_{i}1001wi100
题解
按照题目意思对于q个人我们都要跑一次最短路直接爆掉 我们注意到wi很小范围是100以内那我们可以这样对于辣味x如果有三个点辣味等于x我们可以以他们为起点然后跑bfs去更新与其他点的距离这样跑完相当于知道了其他点到辣味x的城市的最近距离。d[i][j]:表示点j到最近的辣味为i的点之间的距离,然后将dis[i][j]min(dis[i-1][j],dis[i][j])顺着更新(因为可以到达辣度小于等于i的点) 辣味x只需要从1循环到100每次跑多源bfs。最后询问时直接查询即可 总复杂度是O(100(nm)100nq)
代码
我一开始输出用的cout直接被卡了
#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef ONLINE_JUDGE
#elsestartTime clock ();freopen(data.in, r, stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#elseendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn200010;
int w[maxn];
vectorintvec[maxn];
int dis[102][maxn];
int vis[maxn];
int n,m,q;
void bfs(int x){queueintq;for(int i1;in;i){vis[i]0;if(w[i]x){q.push(i);dis[x][i]0;}}while(!q.empty()){int uq.front();q.pop();
// vis[u]1;for(auto v:vec[u]){if(vis[v])continue;vis[v]1;dis[x][v]min(dis[x][u]1,dis[x][v]);q.push(v);}}
}
int main()
{rd_test();read(n,m,q);for(int i1;in;i){for(int j0;j100;j){dis[j][i]INF_int;}}for(int i1;in;i)read(w[i]); for(int i1;im;i){int u,v;read(u,v);vec[u].push_back(v);vec[v].push_back(u);}for(int i1;i100;i)bfs(i);for(int i1;in;i){for(int j1;j100;j){dis[j][i]min(dis[j][i],dis[j-1][i]);} }for(int i1;iq;i){int p,a;//位置 辣度 read(p,a);printf(%d\n,(dis[a][p]INF_int?-1:dis[a][p]));}return 0;//Time_test();
}
