Submission #26258

#TimeUsernameProblemLanguageResultExecution timeMemory
26258sgtlaughCities (BOI16_cities)C++14
100 / 100
2756 ms43876 KiB
#include <stdio.h> #include <bits/stdtr1c++.h> #define MAXK 5 #define MAXN 100010 #define clr(ar) memset(ar, 0, sizeof(ar)) #define read() freopen("lol.txt", "r", stdin) #define dbg(x) cout << #x << " = " << x << endl #define ran(a, b) ((((rand() << 15) ^ rand()) % ((b) - (a) + 1)) + (a)) using namespace std; const long long INF = 1LL << 60; bitset <MAXN> visited; int n, k, m, special[MAXK]; long long dis[1 << MAXK][MAXN]; vector <pair<int, int> > graph[MAXN]; void dijkstra(long long dis[MAXN]){ int i, j, v, w; priority_queue <pair<long long, int> > PQ; for (i = 1; i <= n; i++){ visited[i] = 0; if (dis[i] < INF) PQ.push(make_pair(-dis[i], i)); } while (!PQ.empty()){ pair <long long, int> cur = PQ.top(); PQ.pop(); if (!visited[cur.second] && -cur.first == dis[cur.second]){ i = cur.second, visited[i] = 1; for (j = 0; j < graph[i].size(); j++){ v = graph[i][j].first, w = graph[i][j].second; if (dis[v] > dis[i] + w){ dis[v] = dis[i] + w; PQ.push(make_pair(-dis[v], v)); } } } } } long long minimumSteinerTree(){ int i, j, mask, submask; for (mask = 1; mask < (1 << k); mask++){ for (i = 1; i <= n; i++) dis[mask][i] = INF; if (__builtin_popcount(mask) == 1){ dis[mask][special[31 - __builtin_clz(mask)]] = 0; } else{ for (i = 1; i <= n; i++){ for (submask = mask - 1; submask >= (submask ^ mask); submask = (submask - 1) & mask){ dis[mask][i] = min(dis[mask][i], dis[submask][i] + dis[submask ^ mask][i]); } } } dijkstra(dis[mask]); } return *std::min_element(dis[mask - 1] + 1, dis[mask - 1] + 1 + n); } int main(){ int i, j, u, v, w; while (scanf("%d %d %d", &n, &k, &m) != EOF){ for (i = 0; i < MAXN; i++) graph[i].clear(); for (i = 0; i < k; i++) scanf("%d", &special[i]); for (i = 0; i < m; i++){ scanf("%d %d %d", &u, &v, &w); graph[u].push_back(make_pair(v, w)); graph[v].push_back(make_pair(u, w)); } printf("%lld\n", minimumSteinerTree()); } return 0; }

Compilation message (stderr)

cities.cpp: In function 'void dijkstra(long long int*)':
cities.cpp:33:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (j = 0; j < graph[i].size(); j++){
                           ^
cities.cpp: In function 'long long int minimumSteinerTree()':
cities.cpp:45:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j, mask, submask;
            ^
cities.cpp: In function 'int main()':
cities.cpp:66:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j, u, v, w;
            ^
cities.cpp:70:57: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         for (i = 0; i < k; i++) scanf("%d", &special[i]);
                                                         ^
cities.cpp:73:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d %d", &u, &v, &w);
                                          ^
#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...