oj.uz

Submission #84256

# Submission time Handle Problem Language Result Execution time Memory
84256 2018-11-14T03:39:31 Z aome Cities (BOI16_cities) C++17
100 / 100
 5951 ms 137000 KB 
#include <bits/stdc++.h>
using namespace std;
 
struct State {
	int node; int64_t d; int mask;
	State(int _node = 0, int64_t _d = 1e15, int _mask = 0) :
		node(_node), d(_d), mask(_mask) {}
	bool operator<(const State &x) const {
		return d > x.d;
	}
};
 
 
const int N = 100005;
int n, k, m;
int64_t d[N][32];
queue<State> q;
vector<pair<int, int> > G[N];
 
int32_t main(){
	memset(d, 127, sizeof d);
 
	scanf("%d%d%d", &n, &k, &m);
	for(int i = 0; i < k; ++ i) {
		int a; scanf("%d", &a);
		d[a][1 << i] = 0, q.push(State(a, 0, 1 << i));
	}
	for(int i = 1; i <= m; ++ i) {
		int u, v, c; scanf("%d%d%d", &u, &v, &c);
		G[u].push_back(make_pair(c, v));
		G[v].push_back(make_pair(c, u));
	}
 
	while(!q.empty()) {
		auto cur = q.front(); q.pop();
		if(d[cur.node][cur.mask] != cur.d) continue;
 
		for(int i = 0; i < k; ++ i) if((cur.mask & (1 << i)) == 0) for(auto u : G[cur.node]) {
			if(d[cur.node][(1 << i) | cur.mask] > cur.d + d[u.second][1 << i] + u.first) {
				d[cur.node][(1 << i) | cur.mask] = cur.d + d[u.second][1 << i] + u.first;
				q.push(State(cur.node, d[cur.node][(1 << i) | cur.mask], (1 << i) | cur.mask));
			}
			if(d[u.second][(1 << i) | cur.mask] > cur.d + d[u.second][1 << i] + u.first) {
				d[u.second][(1 << i) | cur.mask] = cur.d + d[u.second][1 << i] + u.first;
				q.push(State(u.second, d[u.second][(1 << i) | cur.mask], (1 << i) | cur.mask));
			}
		}
 
		for(auto u : G[cur.node])
			if(d[u.second][cur.mask] > cur.d + u.first) {
				d[u.second][cur.mask] = cur.d + u.first;
				q.push(State(u.second, d[u.second][cur.mask], cur.mask));
			}
	}
 
	int64_t Ans = 1e15;
	for(int i = 1; i <= n; ++ i) Ans = min(Ans, d[i][(1 << k) - 1]);
	cout << Ans << endl;
}

Compilation message

cities.cpp: In function 'int32_t main()':
cities.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &k, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
cities.cpp:25:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a; scanf("%d", &a);
          ~~~~~^~~~~~~~~~
cities.cpp:29:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v, c; scanf("%d%d%d", &u, &v, &c);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 27768 KB Output is correct
2 Correct 25 ms 27872 KB Output is correct
3 Correct 25 ms 27976 KB Output is correct
4 Correct 24 ms 27996 KB Output is correct
5 Correct 24 ms 27996 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 932 ms 51076 KB Output is correct
2 Correct 739 ms 51076 KB Output is correct
3 Correct 212 ms 51076 KB Output is correct
4 Correct 174 ms 51076 KB Output is correct
5 Correct 423 ms 51076 KB Output is correct
6 Correct 139 ms 51076 KB Output is correct
7 Correct 27 ms 51076 KB Output is correct
8 Correct 26 ms 51076 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 51076 KB Output is correct
2 Correct 30 ms 51076 KB Output is correct
3 Correct 31 ms 51076 KB Output is correct
4 Correct 34 ms 51076 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2233 ms 76520 KB Output is correct
2 Correct 1940 ms 77536 KB Output is correct
3 Correct 388 ms 77536 KB Output is correct
4 Correct 1485 ms 77536 KB Output is correct
5 Correct 454 ms 77536 KB Output is correct
6 Correct 245 ms 77536 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4775 ms 137000 KB Output is correct
2 Correct 5951 ms 137000 KB Output is correct
3 Correct 4464 ms 137000 KB Output is correct
4 Correct 741 ms 137000 KB Output is correct
5 Correct 4270 ms 137000 KB Output is correct
6 Correct 832 ms 137000 KB Output is correct
7 Correct 532 ms 137000 KB Output is correct