牛客小白月赛102:最短？路径（分层bfs）

链接：登录—专业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

输出

复制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();}
}