/******************************************************************************
Online C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include <bits/stdc++.h>
using namespace std;
const long long int base = 3e18;
int main()
{
int n,e,k;
cin>>n>>e>>k;
vector<vector<pair<int,long long int>>> arr(n);
int vot[k];
for(int i = 0;i<k;i++)cin>>vot[i];
for(int i = 0;i<e;i++){
int a,b,c;
cin>>a>>b>>c;
arr[a].push_back({b,c});
}
int mask = 0;
int qu;
cin>>qu;
long long int ticket[5];
while(qu--){
int s;
cin>>s>>ticket[0]>>ticket[1]>>ticket[2]>>ticket[3]>>ticket[4];
priority_queue<vector<long long int> , vector<vector<long long int>>, greater<vector<long long int>>> q;
for(int i = 0;i<5;i++)if(ticket[i]==-1)mask|=((1<<i));
vector<long long int> dist(n,(long long int) base);
dist[s]=0;
q.push({0,s,mask});
while(!q.empty()){
long long int d = q.top()[0];
int u = q.top()[1];
int tick = q.top()[2];
q.pop();
if(dist[u]!=d)continue;
for(auto p : arr[u]){
int v = p.first;
long long int di = p.second;
for(int i = 0;i<5;i++){
if((tick&(1<<i)))continue;
if(d+ (di/10)*(10-i-1) +ticket[i]>=dist[v])continue;
int nt = tick;
nt|=((1<<i));
dist[v]=d+ (di/10)*(10-i-1) +ticket[i];
// cout<<d+ (di/10)*(10-i-1) +ticket[i]<<endl;
q.push({dist[v],v,nt});
}
}
}
long long int mx = base;
for(int i = 0;i<k;i++)mx=min(mx,dist[vot[i]]);
if(mx==base){
cout<<-1<<endl;
continue;
}else{
cout<<mx<<endl;
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
7 ms |
856 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
7 ms |
856 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
7 ms |
856 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
7 ms |
856 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
7 ms |
856 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
7 ms |
860 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
7 ms |
856 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |