题目链接：https://codeforces.com/problemset/problem/1547/E

这个题意比较容易理解，就是让我们求每个空格的最低温度，这道题目可以用最短路解决，我们可以让每两个相邻的点的距离为1，然后建立一个虚拟源点，把每个装有空调的格子与虚拟源点连一条边，权值为空调的温度，最后直接跑一个dijkstra就可以求得答案，下面是代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
const int N=1e6;
int h[N],e[N],ne[N],w[N],idx,dist[N];
bool vis[N];
int p[N];
void add(int x,int y,int z)
{e[idx]=y;w[idx]=z;ne[idx]=h[x];h[x]=idx++;
}
void dijkstra()
{priority_queue<PII,vector<PII>,greater<PII> >q;q.push({0,0});dist[0]=0;while(q.size()){int begin=q.top().second;q.pop();if(vis[begin]) continue;vis[begin]=true;for(int i=h[begin];i!=-1;i=ne[i]){int j=e[i];if(dist[j]>dist[begin]+w[i]){dist[j]=dist[begin]+w[i];q.push({dist[j],j});}}}return ;
}
int main()
{int q;cin>>q;while(q--){int n,k;scanf("%d%d",&n,&k);//建立虚拟源点h数组要从0开始赋值 for(int i=0;i<=n;i++)//用memset会超时（memset会对整个数组赋初值） {h[i]=-1;dist[i]=0x3f3f3f3f;vis[i]=false;}idx=0;for(int i=1;i<=k;i++)scanf("%d",&p[i]);int t;for(int i=1;i<=k;i++)//建立虚拟远点与有空调的格子的有权边 {scanf("%d",&t);add(0,p[i],t);} for(int i=1;i<n;i++){add(i,i+1,1);add(i+1,i,1);}dijkstra();for(int i=1;i<=n;i++)printf("%d ",dist[i]);puts(""); }return 0;
}

下面再分享一种做法：

我们考虑第i个格子的温度与哪些点的关系最密切，不难想到他与两边相邻的格子关系最为密切，要么就是由左边格子更新，要么就是由右边的格子更新，亦或者是自己本身的值，有了这个想法之后我们就可以用动态规划来做这道题目，动态转移方程就是t [ i ]=min( t [ i ] , t [ i -1 ]),和t [ i ]=min( t [ i ] , t [ i +1 ])，下面是代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
const int N=1e6+10;
int dp[N],p[N];
int main()
{int q;cin>>q;while(q--){int n,k;scanf("%d%d",&n,&k);for(int i=1;i<=n;i++)dp[i]=0x3f3f3f3f;for(int i=1;i<=k;i++)scanf("%d",&p[i]);int t;for(int i=1;i<=k;i++){scanf("%d",&t);dp[p[i]]=t;}for(int i=2;i<=n;i++)//由左向右更新 dp[i]=min(dp[i-1]+1,dp[i]);for(int i=n-1;i>=1;i--)//由右向左更新 dp[i]=min(dp[i+1]+1,dp[i]);for(int i=1;i<=n;i++)printf("%d ",dp[i]);puts("");}return 0;
}