#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int>ii;
#define fi first
#define se second
#define name "main"
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(b);i>=(a);--i)
#define N 5'00'0
const LL INF=(LL)1e18;
vector<ii>ke[N+2];
void add_canh(int u,int v,int c){
ke[u].push_back({v,c}); return;
}
struct Point{
LL cost;
int u;
int i1,i2,i3,i4,i5;
bool operator <(const Point&other) const{
return cost>other.cost;
}
};
int cnt[6]={};
LL d[N+2][2][2][2][2][2],p[6]={},price[6]={};
bool voting[N+2];
int n,m,k;
LL djisktra(int source){
FOR(i,1,n){
FOR(i1,0,1) FOR(i2,0,1) FOR(i3,0,1) FOR(i4,0,1) FOR(i5,0,1) d[i][i1][i2][i3][i4][i5]=INF;
}
priority_queue<Point>q;
FOR(i1,0,cnt[1]) FOR(i2,0,cnt[2]) FOR(i3,0,cnt[3]) FOR(i4,0,cnt[4]) FOR(i5,0,cnt[5]){
LL c=price[1]*i1+price[2]*i2+price[3]*i3+price[4]*i4+price[5]*i5;
d[source][i1][i2][i3][i4][i5]=c;
q.push({d[source][i1][i2][i3][i4][i5],source,i1,i2,i3,i4,i5});
}
LL ans=INF;
while (q.size()){
LL cost=q.top().cost;
int u=q.top().u,i1=q.top().i1,i2=q.top().i2,i3=q.top().i3,i4=q.top().i4,i5=q.top().i5;
q.pop();
// cout<<u<<' '<<i1<<' '<<i2<<' '<<i3<<' '<<i4<<' '<<i5<<' '<<cost<<' '<<d[u][i1][i2][i3][i4][i5]<<'\n';
if (cost!=d[u][i1][i2][i3][i4][i5]) continue;
if (voting[u]) {
ans=cost;
break;
}
for(auto&v:ke[u]){
// cout<<v.fi<<' '<<v.se<<' '<<d[u][i1][i2][i3][i4][i5]<<'\n';
if (d[v.fi][i1][i2][i3][i4][i5]>d[u][i1][i2][i3][i4][i5]+v.se){
d[v.fi][i1][i2][i3][i4][i5]=d[u][i1][i2][i3][i4][i5]+v.se;
q.push({d[v.fi][i1][i2][i3][i4][i5],v.fi,i1,i2,i3,i4,i5});
// cout<<v.fi<<' '<<v.se<<' '<<d[u][i1][i2][i3][i4][i5]<<'\n';
}
if (i1-1>=0&&d[v.fi][i1-1][i2][i3][i4][i5]>d[u][i1][i2][i3][i4][i5]+v.se-v.se*p[1]/10){
d[v.fi][i1-1][i2][i3][i4][i5]=d[u][i1][i2][i3][i4][i5]+v.se-v.se*p[1]/10;
q.push({d[v.fi][i1-1][i2][i3][i4][i5],v.fi,i1-1,i2,i3,i4,i5});
}
if (i2-1>=0&&d[v.fi][i1][i2-1][i3][i4][i5]>d[u][i1][i2][i3][i4][i5]+v.se-v.se*p[2]/10){
d[v.fi][i1][i2-1][i3][i4][i5]=d[u][i1][i2][i3][i4][i5]+v.se-v.se*p[2]/10;
q.push({d[v.fi][i1][i2-1][i3][i4][i5],v.fi,i1,i2-1,i3,i4,i5});
}
if (i3-1>=0&&d[v.fi][i1][i2][i3-1][i4][i5]>d[u][i1][i2][i3][i4][i5]+v.se-v.se*p[3]/10){
d[v.fi][i1][i2][i3-1][i4][i5]=d[u][i1][i2][i3][i4][i5]+v.se-v.se*p[3]/10;
q.push({d[v.fi][i1][i2][i3-1][i4][i5],v.fi,i1,i2,i3-1,i4,i5});
}
if (i4-1>=0&&d[v.fi][i1][i2][i3][i4-1][i5]>d[u][i1][i2][i3][i4][i5]+v.se-v.se*p[4]/10){
d[v.fi][i1][i2][i3][i4-1][i5]=d[u][i1][i2][i3][i4][i5]+v.se-v.se*p[4]/10;
q.push({d[v.fi][i1][i2][i3][i4-1][i5],v.fi,i1,i2,i3,i4-1,i5});
}
if (i5-1>=0&&d[v.fi][i1][i2][i3][i4][i5-1]>d[u][i1][i2][i3][i4][i5]+v.se-v.se*p[5]/10){
d[v.fi][i1][i2][i3][i4][i5-1]=d[u][i1][i2][i3][i4][i5]+v.se-v.se*p[5]/10;
q.push({d[v.fi][i1][i2][i3][i4][i5-1],v.fi,i1,i2,i3,i4,i5-1});
}
}
}
return (ans==INF?-1:ans);
}
int32_t main(){
scanf("%d%d%d",&n,&m,&k);
FOR(i,1,k) {
int x; scanf("%d",&x);
voting[x+1]=true;
}
FOR(i,1,m) {
int u,v,c; scanf("%d%d%d",&u,&v,&c);
++u,++v;
add_canh(u,v,c);
}
int q;scanf("%d",&q);
while(q--){
int source; scanf("%d",&source);++source;
FOR(i,1,5) {
scanf("%lld",&price[i]);
if (price[i]==-1) cnt[i]=0; else cnt[i]=1;
p[i]=i;
}
printf("%lld\n",djisktra(source));
}
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'int32_t main()':
Main.cpp:86:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
86 | scanf("%d%d%d",&n,&m,&k);
| ~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:88:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
88 | int x; scanf("%d",&x);
| ~~~~~^~~~~~~~~
Main.cpp:92:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
92 | int u,v,c; scanf("%d%d%d",&u,&v,&c);
| ~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:96:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
96 | int q;scanf("%d",&q);
| ~~~~~^~~~~~~~~
Main.cpp:98:26: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
98 | int source; scanf("%d",&source);++source;
| ~~~~~^~~~~~~~~~~~~~
Main.cpp:100:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
100 | scanf("%lld",&price[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |