多维最短路

D-最短？路径_牛客小白月赛102 (nowcoder.com)

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6;
struct node {int x;int y;int z;bool operator>(const node& other) const {return x> other.x;}
};
signed main()
{ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);int t;cin>>t;while(t--){int n,m,k;cin>>n>>m>>k;vector<int> a(n+5);vector<vector<int>> g(n+5);for(int i=1;i<=n;i++)cin>>a[i];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<node,vector<node>,greater<node>>q; vector<vector<int>> vis(n+5,vector<int>(k+5));vector<vector<int>> ans(n+5,vector<int>(k+5,1e18));if(k!=0){q.push({1,1,1});ans[1][1]=1;}q.push({a[1],1,0});ans[1][0]=a[1];while(!q.empty()){node xx=q.top();int cost=xx.x;int now=xx.y;int cnt=xx.z;q.pop();if(vis[now][cnt])continue;vis[now][cnt]=1;for(auto it:g[now]){if(ans[it][0]>cost+a[it]){ans[it][0]=cost+a[it];q.push({cost+a[it],it,0});}if(cnt+1<=k&&ans[it][cnt+1]>cost+1)	{ans[it][cnt+1]=cost+1;q.push({cost+1,it,cnt+1});}}}int minans=1e18;for(int i=0;i<=k;i++)minans=min(minans,ans[n][i]);cout<<minans<<'\n';		}}