国外客户的网站电话,网站是哪个建站公司做的,php7 wordpress速度,什么值得买网站模板Moving On Gym - 102222F
题意#xff1a;
有 n 个城市#xff0c;q 次询问.
给出每个城市的危险度 r 和 城市的邻接矩阵.
每次询问给出 u、v、w#xff0c;求从 u 到 v 且不经过其他危险度超过 w 的城市的最短路.
题解#xff1a;
floyd 变形 我队友一开始想的是每次…Moving On Gym - 102222F
题意
有 n 个城市q 次询问.
给出每个城市的危险度 r 和 城市的邻接矩阵.
每次询问给出 u、v、w求从 u 到 v 且不经过其他危险度超过 w 的城市的最短路.
题解
floyd 变形 我队友一开始想的是每次加点然后跑dij但是肯定会超时 我想的是给出起点和终点选出满足条件的城市然后用这些城市去更新最短路径 在本题中就是利用floyd来做一半来说第三层循环是枚举中间变量k我们将其提到最外面对于每一次询问都有一个危险值上限w我们根据这个w筛选出危险值小于w的所有点即城市然后依次跑更新操作等全部跑完此时询问的两个城市之间的路径长度即为最短路且所有城市危险值不会超过w 方法二 我还看到一个做法 dp[k][i][j]表示最大权值为所有权值k大的i到j的最短路距离 对城市的危险值排序依次加点更新不同层次的最短路 最后读入直接输出 我感觉两个方法本质应该差不多
代码
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int maxn300;
const int maxm2e49;
int dis[maxn][maxn];
struct node{int u,v,w;int id;
}qq[maxm];
struct nod
{int id,r;
}a[maxn];
int ans[maxm];
bool cmp(node a,node b)
{return a.wb.w;
}
bool cmp1(nod a,nod b)
{return a.rb.r;
}
int main()
{int t;cint;for(int tt1;ttt;tt){//memset(dis,0x3f,sizeof dis);//memset(ans,0,sizeof ans);int n,q;scanf(%d%d,n,q);//cinnq;for(int i1;in;i){scanf(%d,a[i].r);//cina[i].r;a[i].idi;}for(int i1;in;i){for(int j1;jn;j){scanf(%d,dis[i][j]);//cindis[i][j];}}for(int i1;iq;i){int u,v,w;scanf(%d%d%d,qq[i].u,qq[i].v,qq[i].w);//cinqq[i].uqq[i].vqq[i].w;qq[i].idi;}sort(qq1,qq1q,cmp);sort(a1,a1n,cmp1);int cur1;for(int xx1;xxq;xx)//q*n*n*?n{while(a[cur].rqq[xx].wcurn){int ka[cur].id;for(int i1;in;i){for(int j1;jn;j){dis[i][j]min(dis[i][k]dis[k][j],dis[i][j]);}}cur;}ans[qq[xx].id]dis[qq[xx].u][qq[xx].v];}
// for(int i1;in;i)
// {
//
// for(int ji;jn;j)
// {
// if(ij)
// {
// dis[i][j]0;
// dis[j][i]0;
// }
// for(int k1;kn;k){
// //if()
// dis[i][j]min(dis[i][k]dis[k][j],dis[i][j]);
// }
// }
// } printf(Case #%d:\n,tt);for(int i1;iq;i){coutans[i]endl;}}return 0;}第二个方法
#includeiostream
#includealgorithm
#includestdio.h
#includestring.h
using namespace std;
int dp[310][310][310];
int has[310];int dan[310];int num[310];bool cmp(int a,int b){return dan[a]dan[b];
}int main(){int t;int cur1;scanf(%d,t);while(t--){int n,m;scanf(%d%d,n,m);memset(dp,0x3f3f3f3f,sizeof(dp));int cnt1;for(int i1;in;i){scanf(%d,dan[i]);num[i]i;}for(int i1;in;i)for(int j1;jn;j)scanf(%d,dp[i][j][0]);sort(num1,num1n,cmp);for(int k1;kn;k){for(int i1;in;i){for(int j1;jn;j){dp[i][j][k]min(dp[i][j][k-1],dp[i][num[k]][k-1]dp[num[k]][j][k-1]);}}}printf(Case #%d:\n,cur);while(m--){int st,ed,w;scanf(%d%d%d,st,ed,w);int ans0;for(int i1;in;i){if(dan[num[i]]w) ansi;}printf(%d\n,dp[st][ed][ans]);}}
}
