优质的网站制作,建站如何收费,个人网站怎么写,最牛的html5网站建设题目
在樱花盛开的季节#xff0c;西湖大学吸引了大量游客#xff0c;这让胥胥非常烦恼。于是#xff0c;他发明了一个神奇的按钮#xff0c;按下按钮后#xff0c;校园里所有的游客都会以光速从最近的大门离开学校。现在#xff0c;胥胥非常好奇#xff0c;游客们以光…题目
在樱花盛开的季节西湖大学吸引了大量游客这让胥胥非常烦恼。于是他发明了一个神奇的按钮按下按钮后校园里所有的游客都会以光速从最近的大门离开学校。现在胥胥非常好奇游客们以光速离开学校时每时每刻所走的距离总和是多少。
具体来说WHU 是一个无向图有 n 个节点和 m 条边。每个节点都有 ai 名游客。在 n 个节点中 k 个节点作为大门每个大门的开启时间间隔为 [,][li,ri] 。问题是从 11 到 T 的每个时刻游客以光速离开校园的距离总和是多少
注 如果有游客无法离开学校则距离之和应假设为 −1−1 。
保证给定数据的图形连通、无自循环和存在多条边。
输入
第一行包含四个整数 n ( 1≤≤1051≤n≤105 ), m ( 1≤≤1051≤m≤105 ), k ( 1≤≤151≤k≤15 ), T ( 1≤≤1051≤T≤105 ).
第二行包含 n 个整数 ai ( 1≤≤1031≤ai≤103 )。( 1≤≤1031≤ai≤103 )代表 i /-th 节点的游客数量。
接下来的每 k 行包含三个整数 pi ( 1≤≤1≤pi≤n )。( 1≤≤1≤pi≤n )、 li 、 ri ( 1≤≤≤1≤li≤ri≤T )代表图中索引为 pi 的节点是 i /第三个大门大门的开启时间是 [,][li,ri] 。
接下来的 m 行中每一行都包含三个整数 ,,u,v,w ( 1≤,≤,1≤≤1031≤u,v≤n,1≤w≤103 )代表 u 和 v 之间长度为 w 的路径。
输出
打印 T 行每行包含一个整数代表 i /-时刻的距离总和
做法
#includebits/stdc.h
#define int long long
using namespace std;const int N1e510;int n,m,k,t,tot;
int a[N],head[N];struct ty{int l,next,t;
}edge[2*N];//无向图没乘以2报超时血泪教训void addedge(int x,int y,int z){edge[tot].lz;edge[tot].nexthead[x];head[x]tot;edge[tot].ty;
}struct ty2{int x,dis;bool operator (const ty2 a) const{return disa.dis;}
};vectorint v[N];//在时间i时开了的大门
unordered_mapint,int mp;//编号1~k 对应的门的编号 直接用一个p[i]数组记录门的编号就好了
int vis[20][N],dis[20][N];//门到各个点的最短路
vectorpairint,int g[N];//每个点i到k个门的距离
vectorint g1[N];每个点i到k个门的距离 从小到大priority_queuety2 q;
void dij(int k){q.push({mp[k],0});dis[k][mp[k]]0;while(q.size()){ty2 tmpq.top();q.pop();if(vis[k][tmp.x]) continue;vis[k][tmp.x]1;for(int ihead[tmp.x];i!-1;iedge[i].next){if(vis[k][edge[i].t]) continue;if(dis[k][tmp.x]edge[i].ldis[k][edge[i].t]){dis[k][edge[i].t]dis[k][tmp.x]edge[i].l;q.push({edge[i].t,dis[k][edge[i].t]});}}}
}signed main(){memset(head,-1,sizeof(head));scanf(%lld%lld%lld%lld,n,m,k,t);for(int i1;in;i) scanf(%lld,a[i]);for(int i1;ik;i){int p,l,r;scanf(%lld%lld%lld,p,l,r);mp[i]p;//门 for(int jl;jr;j){//时间 v[j].push_back(i);}}for(int i1;im;i){int u,v,w;scanf(%lld%lld%lld,u,v,w);addedge(u,v,w);addedge(v,u,w);}for(int i1;ik;i){for(int j1;jn;j){dis[i][j]0x3f3f3f3f3f3f3f3f;}}for(int i1;ik;i)//求门到各个点的最短路dij(i);for(int i1;in;i) {for(int j1;jk;j) {g[i].push_back({dis[j][i],j});}sort(g[i].begin(),g[i].end());for(int j0;jk;j) {g1[i].push_back(g[i][j].second);//每个点i到k个门的距离 从小到大}}int ans0;for(int i1;it;i){ if(v[i].size()0) {//没有门打开出不去 cout-1endl;continue;}if(v[i]v[i-1]){//不加会超时因为有很多情况都是只开了那几个门coutansendl;continue;}ans0;for(int j1;jn;j){for(int k0;kg1[j].size();k){//门 按距离从小到大if(count(v[i].begin(),v[i].end(),g1[j][k])){//先找到肯定是最小的最短路ansa[j]*dis[g1[j][k]][j];break;}}}coutansendl;}}
wa的原因
一直T在样例2结果是建边的那个数组开少了一半……还有那个特判v[i]v[i-1]也没想到
