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

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

article 2024/9/21 0:37:02

题目

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

具体来说，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;
		
	}
	
}