Submission #132507

#	Time	Username	Problem	Language	Result	Execution time	Memory
132507		arman_ferdous	Cities (BOI16_cities)	C++14	0 / 100	6095 ms	17520 KiB

cities

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ii = pair<ll,int>;
const int N = 1e5+100;
const int M = 2e5+100;
const ll oo = 1e18;

int n, k, m, l[M], r[M], cnt[M], sp[5];
ll c[M];
vector<int> g[N];

ll d[N]; int par[N];
priority_queue<ii,vector<ii>,greater<ii>> q;
int go(int s, int t, int add) {
	for(int i = 1; i <= n; i++) d[i] = oo;
	d[s] = 0; q.push({0, s});

	while(!q.empty()) {
		auto U = q.top(); q.pop();
		int u = U.second; ll cw = U.first;
		for(int i : g[u]) {
			int v = (l[i] ^ r[i] ^ u); ll w = (cnt[i] ? 0 : c[i]);
			if(d[v] > cw + w) {
				d[v] = cw + w;
				par[v] = i;
				q.push({d[v], v});
			}
		}
	}
	for(int v = t; v != s; ) {
		cnt[par[v]]++;
		v = (l[par[v]] ^ r[par[v]] ^ v);
	}
	return d[t];
}

ll solve() {
	ll ret = oo;
	do {
		for(int i = 0; i < m; i++) cnt[i] = 0;
		ll here = 0;
		for(int i = 1; i < k; i++)
			here += go(sp[i - 1], sp[i], +1);
		ret = min(ret, here);
	} while(next_permutation(sp, sp+k));
	return ret;
}

int 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++) {
		scanf("%d %d %lld", &l[i], &r[i], &c[i]);
		g[l[i]].push_back(i);
		g[r[i]].push_back(i);
	}
	printf("%lld\n", solve());
	return 0;
}

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:52: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:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &sp[i]);
   ~~~~~^~~~~~~~~~~~~~
cities.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %lld", &l[i], &r[i], &c[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 22
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26