求赞!
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PLL;
const ll N=2010,M=2e5+N;
priority_queue<PLL,vector<PLL>,greater<PLL> > q;
ll n,m,k,T,t[N],dis[N],idx,h[N],w[M],g[M],vtx[M],nxt[M];
bool st[N];
void add(ll u,ll e,ll v) {
vtx[++idx]=v;
nxt[idx]=h[u];
h[u]=idx;
w[idx]=max(t[u],t[e]);
g[idx]=e;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
memset(h,-1,sizeof(h));
memset(dis,0x3f,sizeof(dis));
cin>>n>>m>>k>>T;
for(ll i=1;i<=n;i++) cin>>t[i];
for(ll i=1;i<=m;i++) {
ll s;
cin>>s;
add(0,0,s);
}
while(k--) {
ll a,b,c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
dis[0]=0;
q.push({0,0});
while(!q.empty()) {
ll u=q.top().second;
q.pop();
if(st[u]) continue;
st[u]=1;
for(ll i=h[u];i!=-1;i=nxt[i]) {
ll v=vtx[i],t=max(dis[u],dis[g[i]]);
if(dis[v]>t+w[i]) {
dis[v]=t+w[i];
q.push({dis[v],v});
}
}
}
cout<<dis[T];
return 0;
}
AcWing《寒假每日一题2023》拼团优惠!https://www.acwing.com/activity/content/introduction/2712/group_buy/137158/
我报过了