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

icpc江西：L. campus（dij最短路）

news 2025/7/28 0:37:10

题目

在樱花盛开的季节，西湖大学吸引了大量游客，这让胥胥非常烦恼。于是，他发明了一个神奇的按钮，按下按钮后，校园里所有的游客都会以光速从最近的大门离开学校。现在，胥胥非常好奇，游客们以光速离开学校时，每时每刻所走的距离总和是多少。

具体来说，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 /-时刻的距离总和

做法

#include<bits/stdc++.h>
#define int long long
using namespace std;const int N=1e5+10;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].l=z;edge[tot].next=head[x];head[x]=tot;edge[tot].t=y;
}struct ty2{int x,dis;bool operator < (const ty2 & a) const{return dis>a.dis;}
};vector<int> v[N];//在时间i时开了的大门 
unordered_map<int,int> mp;//编号1~k 对应的门的编号 （直接用一个p[i]数组记录门的编号就好了）
int vis[20][N],dis[20][N];//门到各个点的最短路 
vector<pair<int,int> > g[N];//每个点i到k个门的距离  
vector<int> g1[N];每个点i到k个门的距离 （从小到大）priority_queue<ty2> q;
void dij(int k){q.push({mp[k],0});dis[k][mp[k]]=0;while(q.size()){ty2 tmp=q.top();q.pop();if(vis[k][tmp.x]) continue;vis[k][tmp.x]=1;for(int i=head[tmp.x];i!=-1;i=edge[i].next){if(vis[k][edge[i].t]) continue;if(dis[k][tmp.x]+edge[i].l<dis[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 i=1;i<=n;i++) scanf("%lld",&a[i]);for(int i=1;i<=k;i++){int p,l,r;scanf("%lld%lld%lld",&p,&l,&r);mp[i]=p;//门 for(int j=l;j<=r;j++){//时间 v[j].push_back(i);}}for(int i=1;i<=m;i++){int u,v,w;scanf("%lld%lld%lld",&u,&v,&w);addedge(u,v,w);addedge(v,u,w);}for(int i=1;i<=k;i++){for(int j=1;j<=n;j++){dis[i][j]=0x3f3f3f3f3f3f3f3f;}}for(int i=1;i<=k;i++)//求门到各个点的最短路dij(i);for(int i=1;i<=n;i++) {for(int j=1;j<=k;j++)	{g[i].push_back({dis[j][i],j});}sort(g[i].begin(),g[i].end());for(int j=0;j<k;j++)	{g1[i].push_back(g[i][j].second);//每个点i到k个门的距离 （从小到大）}}int ans=0;for(int i=1;i<=t;i++){	if(v[i].size()==0) {//没有门打开，出不去 cout<<-1<<endl;continue;}if(v[i]==v[i-1]){//不加会超时，因为有很多情况都是只开了那几个门cout<<ans<<endl;continue;}ans=0;for(int j=1;j<=n;j++){for(int k=0;k<g1[j].size();k++){//门 （按距离从小到大）if(count(v[i].begin(),v[i].end(),g1[j][k])){//先找到肯定是最小的（最短路）ans+=a[j]*dis[g1[j][k]][j];break;}}}cout<<ans<<endl;}}