| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1340592 | jenterjongle45 | Library (JOI18_library) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
using pii = pair<int,int>;
struct A{
int u,w,c;
bool operator<(const A &o)const{
return w>o.w;
}
};
int32_t main(){
int n,m,k;cin>>n>>m>>k;
vector<int> T(k);
vector<vector<pii>> adj(n+1);
for(int &x:T) cin>>x;
while (m--){
int u,v,w;cin>>u>>v>>w;
adj[v].push_back({u,w});
}
vector<vector<int>> d(n+1,vector<int> (1<<5));
priority_queue<A> pq;
int Q;cin>>Q;
while(Q--){
int t;cin>>t;
vector<int> s(5);
for(int &x:s){
cin>>x;
}
for(int i=0;i<n;i++) for(int j=0;j<32;j++) d[i][j]=2e18;
for(int x:T){
for(int i=0;i<32;i++){
d[x][i]=0;
for(int j=0;j<5;j++){
if((1<<j)&i){
d[x][i]+=s[j];
if(s[j]==-1) goto NO;
}
}
pq.push({x,d[x][i],i});
NO:;
}
}
while(!pq.empty()){
auto [u,w,c]=pq.top();pq.pop();
if(u==t){
cout<<w<<"\n";
goto nx;
}
if(w!=d[u][c]) continue;
for(auto x:adj[u]){
auto [v,ww]=x;
for(int i=0;i<5;i++){
if(((1<<i)&c)&&d[v][(c)^(1<<i)]>w+(ww)-ww*(i+1)/10){
d[v][(c)^(1<<i)]=w+(ww)-ww*(i+1)/10;
pq.push({v,d[v][(c)^(1<<i)],(c)^(1<<i)});
}
}
if(d[v][c]>w+ww){
d[v][c]=w+ww;
pq.push({v,w+ww,c});
}
}
}
cout<<-1<<'\n';
nx:;
while(!pq.empty()) pq.pop();
}
}