链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
题目描述
给定一个 nnn 个点 mmm 条边的无向图，LH 打算从点 111 出发去点 nnn。
假如 LH 到达了一个点 iii，那么他可以选择在这个点花费 aia_iai 的时间休息后继续赶路，或者不休息然后花费 111 的时间简单整顿后继续赶路。
LH 不能连续超过 kkk 个节点不休息，问从 111 到 nnn 的最短时间。
注意：假如 LH 到达了点 nnn 也需要选择休息或者不休息。
输入描述:
第一行输入一个整数 T(1≤T≤104)T(1\le T\le 10^4)T(1≤T≤104)，表示测试用例组数。接下来是 TTT 个测试用例。 每个测试用例第一行包含三个整数 n,m,k(2≤n≤2×105,1≤m≤3×105,0≤k≤10)n,m,k(2\le n\le 2\times 10^5,1\le m\le 3\times 10^5,0\le k\le 10)n,m,k(2≤n≤2×105,1≤m≤3×105,0≤k≤10)。 第二行输入 nnn 个整数 ai(0≤ai≤109)a_i(0\le a_i\le 10^9)ai(0≤ai≤109)，表示在第 iii 个点休息需要花费的时间。 随后 mmm 行每行两个整数 u,vu ,vu,v，表示 uuu 和 vvv 之间有一条无向边。
保证输入的图联通，没有重边和自环。
保证所有测试用例 nnn 的和不超过 2×1052\times 10^52×105，mmm 的和不超过 3×1053\times 10^53×105。
输出描述:
对于每个测试用例，输出一个整数，表示 LH 从 111 到 nnn 的最短时间。
示例1
输入
复制1 5 6 2 7 7 3 6 4 4 5 1 3 3 4 5 2 2 4 1 4
1 5 6 2 7 7 3 6 4 4 5 1 3 3 4 5 2 2 4 1 4
输出
复制6
6
说明
一种可能的最优方案为 1−>4−>51->4->51−>4−>5。 其中点 111 和点 444 不休息，在点 555 休息，总时间为 1+1+a5=61+1+a_5=61+1+a5=6。
示例2
输入
复制2 20 30 8 9 10 2 8 1 6 7 10 6 10 7 0 0 3 4 0 7 9 4 3 18 4 8 10 17 6 11 3 7 4 7 14 3 8 10 19 16 8 11 4 13 14 17 14 4 15 12 5 12 17 16 9 5 20 7 2 1 4 10 5 14 15 3 5 17 8 16 6 9 10 16 17 4 2 17 20 10 7 16 1 20 30 3 2 0 2 2 9 6 7 2 5 3 7 1 8 8 8 3 1 0 8 9 1 17 11 8 17 16 14 19 7 6 3 4 10 15 4 9 14 18 20 5 7 8 18 10 3 6 7 1 5 14 13 5 14 3 15 2 12 13 7 3 6 18 2 10 9 3 1 14 11 4 3 17 14 10 7 14 13 8 6 5
2 20 30 8 9 10 2 8 1 6 7 10 6 10 7 0 0 3 4 0 7 9 4 3 18 4 8 10 17 6 11 3 7 4 7 14 3 8 10 19 16 8 11 4 13 14 17 14 4 15 12 5 12 17 16 9 5 20 7 2 1 4 10 5 14 15 3 5 17 8 16 6 9 10 16 17 4 2 17 20 10 7 16 1 20 30 3 2 0 2 2 9 6 7 2 5 3 7 1 8 8 8 3 1 0 8 9 1 17 11 8 17 16 14 19 7 6 3 4 10 15 4 9 14 18 20 5 7 8 18 10 3 6 7 1 5 14 13 5 14 3 15 2 12 13 7 3 6 18 2 10 9 3 1 14 11 4 3 17 14 10 7 14 13 8 6 5
输出
复制3 5
3 5
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,m,k,a[N];
int vis[N][20],dis[N][20];
struct ty{
int dis,x,k;
bool operator < (const ty &a) const{
return dis>a.dis;
}
};
void solved(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++){
vis[i][j]=0;
dis[i][j]=0x3f3f3f3f3f3f3f3f;
}
}
vector<int> g[n+1];
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
priority_queue<ty> q;
q.push({a[1],1,0});//休息
dis[1][0]=a[1];
if(k!=0){
q.push({1,1,1});
dis[1][1]=1;
}
while(q.size()){
ty tmp=q.top();
q.pop();
if(vis[tmp.x][tmp.k]) continue;
vis[tmp.x][tmp.k]=1;
for(auto x:g[tmp.x]){
if(tmp.k==k){
if(dis[x][0]>dis[tmp.x][tmp.k]+a[x]){//休息
dis[x][0]=dis[tmp.x][tmp.k]+a[x];
q.push({dis[x][0],x,0});
}
continue;
}
if(dis[x][0]>dis[tmp.x][tmp.k]+a[x]){//休息
dis[x][0]=dis[tmp.x][tmp.k]+a[x];
q.push({dis[x][0],x,0});
}
if(dis[x][tmp.k+1]>dis[tmp.x][tmp.k]+1){
dis[x][tmp.k+1]=dis[tmp.x][tmp.k]+1;
q.push({dis[x][tmp.k+1],x,tmp.k+1});
}
}
}
int ans=0x3f3f3f3f3f3f3f3f;
for(int i=0;i<=k;i++){
ans=min(ans,dis[n][i]);
}
cout<<ans<<endl;
}
signed main(){
cin.tie(0);
ios::sync_with_stdio(0);
int t;
cin>>t;
while(t--){
solved();
}
}
