Submission #84237

#	Time	Username	Problem	Language	Result	Execution time	Memory
84237		ToMoClone	Cities (BOI16_cities)	C++17	0 / 100	6061 ms	133548 KiB

cities

/*input
4 3 6
1 3 4
1 2 4
1 3 9
1 4 6
2 3 2
2 4 5
3 4 8
*/
#include <bits/stdc++.h>
using namespace std;
 
const int N = 100005;
const int64_t inf = 1e15;
 
struct State {
	int node; int64_t d; int mask;
	State(int _node = 0, int64_t _d = inf, int _mask = 0) :
		node(_node), d(_d), mask(_mask) {}
	bool operator<(const State &x) const {
		return d > x.d;
	}
};
 
int n, k, m, mark[N];
int64_t d[N][32];
priority_queue<State> q;
vector<pair<int, int> > G[N];
 
int32_t main(){
	memset(mark, -1, sizeof mark), memset(d, 127, sizeof d);
 
	scanf("%d%d%d", &n, &k, &m);
	for(int i = 0; i < k; ++ i) {
		int a; scanf("%d", &a); mark[a] = i;
		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.top(); q.pop();
		if(cur.mask == (1 << k) - 1) return cout << cur.d << endl, 0;
		for(auto u : G[cur.node])
			if(d[u.second][cur.mask] > d[cur.node][cur.mask] + u.first) {
				d[u.second][cur.mask] = d[cur.node][cur.mask] + u.first;
				q.push(State(u.second, d[u.second][cur.mask], cur.mask));
			}

		for(auto u : G[cur.node]) for(int i = 0; i < k; ++ i) if((!(cur.mask >> i) & 1)) {
			int mask = cur.mask | (1 << i);
			if(d[cur.node][mask] > cur.d + d[u.second][1 << i] + u.first) {
				d[cur.node][mask] = cur.d + d[u.second][1 << i] + u.first;
				q.push(State(cur.node, d[cur.node][mask], mask));
			}
			if(d[u.second][mask] > cur.d + d[u.second][1 << i] + u.first) {
				d[u.second][mask] = cur.d + d[u.second][1 << i] + u.first;
				q.push(State(u.second, d[u.second][mask], mask));
			}
		}
	}
}

Compilation message (stderr)

cities.cpp: In function 'int32_t main()':
cities.cpp:34: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:36:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a; scanf("%d", &a); mark[a] = i;
          ~~~~~^~~~~~~~~~
cities.cpp:40: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: 0 / 22
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26