Submission #281790

#TimeUsernameProblemLanguageResultExecution timeMemory
2817903zpCities (BOI16_cities)C++14
100 / 100
1300 ms34688 KiB
#include<bits/stdc++.h> #define ll long long using namespace std; const int mN = 2e5 + 9; int Sp[mN]; ll D[5][mN], F[5][5][mN], Vis[mN]; vector<pair<int,ll> > V[mN]; int n, k, m; void dij(int a, int b, ll *Ans){ priority_queue<pair<ll, int> > Q; for(int i = 1; i <= n; i++){ Vis[i] = 0; if(b == 0) Ans[i] = 1e18; else { Ans[i] = D[a][i] + D[b][i]; Q.push({-Ans[i], i}); } } if(b == 0){ Ans[a] = 0; Q.push({0, a}); } while(Q.size()){ int x = Q.top().second; Q.pop(); if(Vis[x]) continue; Vis[x] = 1; for(auto E : V[x]){ int y = E.first, l = E.second; if(!Vis[y] && Ans[y] > Ans[x] + l){ Ans[y] = Ans[x] + l; Q.push({-Ans[y], y}); } } } } main(){ scanf("%d %d %d", &n, &k, &m); for(int i = 0; i < k; i++){ scanf("%d", &Sp[i]); } for(int i = 0; i < m; i++){ int a, b, c; scanf("%d %d %d",&a,&b,&c); V[a].push_back({b, c}); V[b].push_back({a, c}); } for(int i =0; i < k; i++){ dij(Sp[i], 0, D[i]); } for(int i = 0; i < k; i++){ for(int j = i+1; j < k; j++){ dij(i, j, F[i][j]); } } if(k == 2){ cout << D[0][Sp[1]] << endl; } if(k == 3){ cout << F[0][1][Sp[2]]<<endl; } if(k == 4){ ll ans = 1e18; vector<int> P = {0,1,2,3}; do{ if(P[0] > P[1] || P[2] > P[3]) continue; for(int i = 1; i <= n; i++) ans = min(ans, D[P[0]][i] + D[P[1]][i] + F[P[2]][P[3]][i]); }while(next_permutation(P.begin(), P.end())); cout<<ans<<endl; } if(k == 5){ ll ans = 1e18; vector<int> P = {0,1,2,3,4}; do{ if(P[1] > P[2] || P[3] > P[4]) continue; for(int i = 1; i <= n; i++) ans = min(ans, D[P[0]][i] + F[P[1]][P[2]][i] +F[P[3]][P[4]][i]); }while(next_permutation(P.begin(), P.end())); cout<<ans<<endl; } }

Compilation message (stderr)

cities.cpp:37:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   37 | main(){
      |      ^
cities.cpp: In function 'int main()':
cities.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |     scanf("%d %d %d", &n, &k, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |         scanf("%d", &Sp[i]);
      |         ~~~~~^~~~~~~~~~~~~~
cities.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |         scanf("%d %d %d",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...