# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1123357 | LTTrungCHL | Voting Cities (NOI22_votingcity) | C++20 | 1095 ms | 7416 KiB |
///***LTT***///
/// ->NHAT QUOC GIA<- ///
#include<bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("popcnt")
#define int long long
#define endl "\n"
#define F first
#define S second
#define pb push_back
using namespace std;
//vector <int> lg2;
//void LOG_ARR(int n){
// lg2.resize(n + 3);
// for (int i = 1;i <= n;++i){
// lg2[i] = __lg(i);
// }
//}
const long long oo = 1e9+7;
const int N = 5000 + 10;
int n, m, k;
int t[N];
pair <int, int> p[7];
vector <pair <int, int>> adj[N];
long long dis[N][34];
void solve(){
cin >> n >> m >> k;
for (int i = 1;i <= k;++i){
cin >> t[i];
}
for (int i = 1;i <= m;++i){
int u, v, w;
cin >> u >> v >> w;
adj[u].pb({v, w});
}
int q;
cin >> q;
while (q--){
int s;
cin >> s;
int sl = 0;
for (int i = 1;i <= 5;++i){
int tmp;
cin >> tmp;
if (tmp != -1){
p[++sl] = {tmp, i};
}
}
for (int i = 0;i < n;++i){
for (int j = 0;j < (1 << sl);++j){
dis[i][j] = oo * oo;
}
}
dis[s][0] = 0;
priority_queue <pair<int,pair <int, int>>> pq;
pq.push({0,{s, 0}});
while (!pq.empty()){
int u = pq.top().S.F;
int mask = pq.top().S.S;
long long d = -pq.top().F;
pq.pop();
if (d > dis[u][mask]) continue;
for (int i = 0;i < adj[u].size();++i){
int v = adj[u][i].F;
int w = adj[u][i].S;
if (d + w < dis[v][mask]){
dis[v][mask] = d + w;
pq.push({-dis[v][mask], {v, mask}});
}
for (int j = 0;j < sl;++j){
if ((1 << j) & mask) continue;
int cost = p[j + 1].F;
int pos = p[j + 1].S;
if (1ll * d + w + cost - (w/10 * pos) < dis[v][mask | (1 << j)]){
dis[v][mask | (1 << j)] = d + w + cost - (w/10 * pos);
pq.push({-dis[v][mask | (1 << j)], {v, mask | (1 << j)}});
}
}
}
}
long long mi = oo * oo;
for (int i = 1;i <= k;++i){
for (int j = 0;j < (1 << sl);++j){
mi = min(mi, dis[t[i]][j]);
}
}
cout << (mi == oo * oo ? - 1 : mi) <<"\n";
}
return;
}
signed main(){
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
cout.tie(NULL);
if (fopen("npt.inp", "r")){
freopen("npt.inp", "r", stdin);
freopen("npt.out", "w", stdout);
}
// int t;
// cin >> t;
// while(t--){
solve();
// }
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | 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... |