Submission #563114

#TimeUsernameProblemLanguageResultExecution timeMemory
563114BobonbushCities (BOI16_cities)C++17
100 / 100
2837 ms45640 KiB
#include <bits/stdc++.h> #define foreach for #define in : using namespace std; typedef long long ll; /* Konichiwa Konichiwa Ara ~~ ara Bob no taisuki - Shinobu Kocho * * * * * * * * * * * I love SHINOBU <3 <3 <3 * * * * * * * * * */ /* _________________________ Author : Bob15324 _________________________ */ template<class X , class Y> bool Minimize(X & x , Y y) { if((x == -1 || x > y) && (y >= 0)) { x = y; return true; } return false; } template<class X , class Y> bool Maximize(X & x , Y y) { if( x < y) { x = y; return true; } return false; } /* End of templates. Let's see what do we have here */ const int N = 1e5+1; const int K = 5; int n , k , m; int special[K]; long long dist[N] , dp[N][1 << K]; class GRAPH { private: vector<vector<pair<int ,int >>>vertices; public: GRAPH(int _n) { vertices.resize(_n+1); } void AddEdge(int u ,int v ,int w) { vertices[u].push_back(make_pair(v , w)); vertices[v].push_back(make_pair(u , w)); } void Dijktra() { priority_queue<pair<long long , int > , vector<pair<long long , int>> , greater<pair<long long , int>>>pq; for(int i = 1; i <= n ; i++) { pq.push(make_pair(dist[i] , i)); } while(!pq.empty()) { pair<long long , int > temp = pq.top(); pq.pop(); int u = temp.second; long long du = temp.first; if(dist[u] < du) { continue; } foreach(pair<int ,int > adj in vertices[u]) { int v = adj.first; int w = adj.second; if(Minimize(dist[v] , dist[u] + w)) { pq.push(make_pair(dist[v] , v)); } } } } }; int main() { ios_base :: sync_with_stdio(0);cin.tie(0); cin >> n >> k >> m; for(int i = 1; i <= n ; i++) { dist[i] = 1e18+1; for(int j = 0 ; j <= (1 << k)-1 ; j++) { dp[i][j] = 1e18+1; } } for(int i = 0; i< k ; i++) { cin >> special[i]; dp[special[i]][1 << i] = 0; } GRAPH graph(n); for(int i = 1; i <= m ; i++) { int u , v , w; cin >> u >> v >> w; graph.AddEdge(u , v , w); } for(int mask = 0 ; mask <= (1 << k )-1 ; mask++) { for(int i = 0 ; i <= (1 << k)-1 ; i++ ) { for(int j = 0 ; j <= (1 << k)-1 ; j++) { if((i | j) == mask) { for(int z = 1 ; z <= n ; z++) { Minimize(dp[z][mask] , dp[z][i] + dp[z][j]); } } } } for(int i = 1 ; i <= n ; i++) { dist[i] = dp[i][mask]; } graph.Dijktra(); for(int i = 1 ; i <= n ; i++) { dp[i][mask] = dist[i]; } } long long res = -1; for(int i = 1; i <= n ; i++) { Minimize(res , dp[i][(1 << k)-1]); } cout << res; return 0; } //Ehem. My code is amazing. Pay me 2$.Thank you.
#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...