| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 878392 |
2023-11-24T09:50:39 Z |
manizare |
Cities (BOI16_cities) |
C++14 |
|
6000 ms |
37496 KB |
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define int long long
#define sz(v) (int)v.size()
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e5 + 10 , inf = 1e18 , mod = 998244353 ;
int cnt= 1, id[maxn] , dis[100][maxn] ,mark[maxn] , n , m , k , A[maxn] , B[maxn] ;
vector<pii> G[maxn];
void dij(int r){
priority_queue <pii> pq ;
if(id[r] !=0)return ;
id[r] = cnt ;
for(int i = 1 ;i <= n ;i++){
dis[cnt][i] = inf ;
mark[i] =0 ;
}
dis[cnt][r] = 0 ;
pq.push({0 , r}) ;
while(pq.size()){
int v = pq.top().S ;
pq.pop() ;
if(mark[v] == 1)continue;
mark[v] = 1;
for(pii u : G[v]){
if(dis[cnt][u.F] > dis[cnt][v]+u.S){
dis[cnt][u.F] = dis[cnt][v] + u.S ;
pq.push({-dis[cnt][u.F] , u.F}) ;
}
}
}
cnt++;
}
int sl2(vector <int> a){
return dis[id[a[0]]][a[1]] ;
}
int sl3(vector <int> a){
int ans = inf ;
vector <int> vec ;
for(int i =1 ; i <= n; i++){
ans = min(ans , dis[id[a[0]]][i] + dis[id[a[1]]][i] + dis[id[a[2]]][i]);
}
return ans ;
}
vector <pair <pii ,int> > ed;
int sl4(vector <int> a){
for(int i = 1; i <= n; i++){
A[i] = dis[id[a[0]]][i] + dis[id[a[1]]][i] ;
B[i] = dis[id[a[2]]][i] + dis[id[a[3]]][i] ;
}
priority_queue<pii> pq ;
for(int i = 1; i <= n; i++){
pq.push({-A[i] , i});
mark[i] =0 ;
}
while(pq.size()){
int v= pq.top().S ;
pq.pop() ;
if(mark[v] == 1)continue;
mark[v] = 1;
for(pii u : G[v]){
if(A[u.F] > A[v] + u.S){
A[u.F] = A[v] + u.S;
pq.push({-A[u.F] , u.F}) ;
}
}
}
for(int i = 1; i <= n; i++){
pq.push({-B[i] , i});
mark[i] = 0;
}
while(pq.size()){
int v= pq.top().S ;
pq.pop() ;
if(mark[v] == 1)continue;
mark[v] = 1;
for(pii u : G[v]){
if(B[u.F] > B[v] + u.S){
B[u.F] = B[v] + u.S;
pq.push({-B[u.F] , u.F}) ;
}
}
}
int ans =inf ;
for(int i = 1 ; i<= n; i++){
int sm =0 ;
ans = min(ans , A[i] + B[i]) ;
for(int x : a){
sm += dis[id[x]][i];
}
ans = min(ans , sm );
}
return ans ;
}
int sl44(vector <int> vec){
int ans = inf ;
for(int i =0 ; i < 4 ; i++){
vector <int> vec2 ;
int f =inf ;
for(int x : vec){
if(x!=vec[i]){
vec2.pb(x);
f = min(f , dis[id[vec[i]]][x]);
}
}
ans = min(ans , f + sl3(vec2)) ;
}
ans = min(ans , sl4(vec)) ;
swap(vec[1] , vec[2]) ;
ans = min(ans , sl4(vec)) ;
swap(vec[1] , vec[3]) ;
ans = min(ans , sl4(vec)) ;
return ans ;
}
int sl5(vector <int> a){
for(int i = 1; i <= n; i++){
A[i] = dis[id[a[0]]][i] + dis[id[a[1]]][i] ;
B[i] = dis[id[a[2]]][i] + dis[id[a[3]]][i] ;
}
priority_queue<pii> pq ;
for(int i = 1; i <= n; i++){
pq.push({-A[i] , i});
mark[i] =0 ;
}
while(pq.size()){
int v= pq.top().S ;
pq.pop() ;
if(mark[v] == 1)continue;
mark[v] = 1;
for(pii u : G[v]){
if(A[u.F] > A[v] + u.S){
A[u.F] = A[v] + u.S;
pq.push({-A[u.F] , u.F}) ;
}
}
}
for(int i = 1; i <= n; i++){
pq.push({-B[i] , i});
mark[i] = 0;
}
while(pq.size()){
int v= pq.top().S ;
pq.pop() ;
if(mark[v] == 1)continue;
mark[v] = 1;
for(pii u : G[v]){
if(B[u.F] > B[v] + u.S){
B[u.F] = B[v] + u.S;
pq.push({-B[u.F] , u.F}) ;
}
}
}
int ans =inf ;
for(int i = 1 ; i<= n; i++){
int sm =0 ;
ans = min(ans , A[i] + B[i] + dis[id[a[4]]][i]) ;
for(int x : a){
sm += dis[id[x]][i];
}
ans = min(ans , sm );
}
for(int i =1 ; i <= n; i++){
B[i] = dis[id[a[2]]][i] + dis[id[a[3]]][i] + dis[id[a[4]]][i];
mark[i] =0 ;
pq.push({-B[i] , i});
}
while(pq.size()){
int v= pq.top().S ;
pq.pop() ;
if(mark[v] == 1)continue;
mark[v] = 1;
for(pii u : G[v]){
if(B[u.F] > B[v] + u.S){
B[u.F] = B[v] + u.S;
pq.push({-B[u.F] , u.F}) ;
}
}
}
for(int i = 1; i <= n; i++){
ans = min(ans , A[i] + B[i]);
}
return ans ;
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n>> k >> m ;
int dd = 0;
vector <int> vec;
for(int i =0 ; i < k ; i++){
int f;
cin >> f ;vec.pb(f);
}
for(int i = 1; i <= m ;i++){
int v, u , c ;
cin >> v >> u >> c ;
ed.pb({{v,u} ,c});
G[v].pb({u,c});
G[u].pb({v,c}) ;
}
for(int x : vec)dij(x);vector <int> p ;
for(int i =0 ; i < 5 ; i++)p.pb(i);
int ans = inf ;
for(int i =0 ; i < 5 ; i++){
int f =0 ;
for(int x : vec){
if(x!=vec[i]){
f = min(f , dis[id[vec[i]]][x]);
}
}
ans = min(ans , sl44(vec) + f) ;
}
do{
vector <int> vec2 ;
for(int i =0 ; i < 5 ; i++){
vec2.pb(vec[p[i]]) ;
}
ans = min(ans , sl5(vec2)) ;
}while(next_permutation(all(p)));
cout << ans << "\n" ;
}
/*
*/
Compilation message
cities.cpp: In function 'int main()':
cities.cpp:208:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
208 | for(int x : vec)dij(x);vector <int> p ;
| ^~~
cities.cpp:208:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
208 | for(int x : vec)dij(x);vector <int> p ;
| ^~~~~~
cities.cpp:195:6: warning: unused variable 'dd' [-Wunused-variable]
195 | int dd = 0;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6042 ms |
33016 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
9084 KB |
Output is correct |
| 2 |
Correct |
74 ms |
9080 KB |
Output is correct |
| 3 |
Correct |
55 ms |
8792 KB |
Output is correct |
| 4 |
Correct |
41 ms |
9056 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6056 ms |
37496 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6084 ms |
37140 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
