P1119 灾后重建

题目地址

题意：给出n个村庄的灾后重建所需时间和m条双向路和它们的路径长，进行q次询问，每次询问两个村庄在时间t时的最短的路径，且路径上所有村庄都已重建，如果不存在或者t时两个村庄都未重建好输出-1

Solution

floyd算法板子题

dp[i][j][k]表示从i中转k到j的最短距离

根据floyd算法，有：

void floyd()
{
    for(k=1;k<=n;k++)
     for(i=1;i<=n;i++)  
     	for(j=1;j<=n;j++)  
     		if(dp[i][j]>dp[i][k]+dp[k][j])  
            	dp[i][j]=dp[i][k]+dp[k][j];
}

但是这题有个附加条件就是沿路村庄都需要重建好，那么就从先重建的村庄开始进行floyd算法即可

void floyd(int k)
{
     for(i=1;i<=n;i++)  
     	for(j=1;j<=n;j++)  
     		if(dp[i][j]>dp[i][k]+dp[k][j])  
            	dp[i][j]=dp[i][k]+dp[k][j];
}

AC代码：

void floyd(int k)
{
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(dp[i][j]>dp[i][k]+dp[k][j])dp[i][j]=dp[i][k]+dp[k][j];
		}
	}
}


void solve()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)cin>>a[i];
	memset(dp,INF,sizeof(dp));
	for(int i=1;i<=m;i++)
	{
		int u,v,w;cin>>u>>v>>w;
		dp[u][v]=dp[v][u]=w;
	}
	
	int q;cin>>q;
	int now=0;
	for(int i=1;i<=q;i++)
	{
		int x,y,t;
		cin>>x>>y>>t;
		if(a[x]>t||a[y]>t)cout<<"-1\n";
		else 
		{
			while(a[now]<=t&&now<n)floyd(now++);
			if(dp[x][y]>=INF)cout<<"-1\n";
			else cout<<dp[x][y]<<"\n";
		}
	}
}