oj.uz

Submission #56161

# Submission time Handle Problem Language Result Execution time Memory
56161 2018-07-10T06:41:25 Z 윤교준(#1582) Cities (BOI16_cities) C++11
0 / 100
 6000 ms 23768 KB 
#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
static unsigned char str[22000022], *p=str;
void fg(vector<pii> G[], int a, int b, int c) { G[a].eb(b, c); G[b].eb(a, c); }

const bool debug = 0;
const int MAXN = 100005;
const int MAXM = 200005;

vector<pii> G[MAXN];

vector<int> BV[MAXN];
ll dp[MAXN];

bitset<MAXN> chk;

int A[MAXM], B[MAXM], C[MAXM];
int D[6];

ll Ans = INFLL;
int N, M, K;

int main() {
	fread(str, 1, 22000022, stdin);
	rf(N) rf(K) rf(M)
	for(int i = 1; i <= K; i++) { rf(D[i]) }
	sort(D+1, D+K+1);
	for(int i = 1; i <= M; i++) {
		rf(A[i]) rf(B[i]) rf(C[i])
		fg(G, A[i], B[i], C[i]);
	}

	do {
		vector<int> V(1, D[1]);
		ll ret = 0;

		for(int di = 2; di <= K; di++) {
			priority_queue<pli, vector<pli>, greater<pli>> PQ;

			for(int i = 1; i <= N; i++) BV[i].clear();
			fill(dp, dp+N+1, INFLL);
			for(int v : V) {
				dp[v] = ret;
				PQ.push(pli(ret, v));
			}

			for(; !PQ.empty();) {
				ll dst; int idx;
				tie(dst, idx) = PQ.top(); PQ.pop();
				if(dp[idx] < dst) continue;
				if(idx == D[di]) break;

				for(auto &e : G[idx]) {
					int nidx = e.first;
					ll ndst = dst + e.second;
					if(dp[nidx] < ndst) continue;
					if(ndst < dp[nidx]) {
						BV[nidx].clear();
						PQ.push(pli(ndst, nidx));
						dp[nidx] = ndst;
					}
					BV[nidx].pb(idx);
				}
			}

			chk.reset();
			for(int v : V) chk[v] = true;
			V.pb(D[di]); chk[D[di]] = true;
			for(int i = 0; i < sz(V); i++) {
				for(int v : BV[V[i]]) {
					if(chk[v]) continue;
					chk[v] = true;
					V.pb(v);
				}
			}

			ret = dp[D[di]];

			if(debug) {
				for(int i = 1; i <= K; i++) printf("%d ", D[i]);
				printf(":: %lld\n", ret);
				printf("di=%d :: ", di);
				for(int v : V) printf("%d ", v);
				puts("\n");
			}
		}

		upmin(Ans, ret);
	} while(next_permutation(D+1, D+K+1));

	cout << Ans << endl;
	return 0;
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:42:7: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  fread(str, 1, 22000022, stdin);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5076 KB Output is correct
2 Correct 9 ms 5096 KB Output is correct
3 Incorrect 7 ms 5148 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 766 ms 23428 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 23428 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 5413 ms 23768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6009 ms 23768 KB Time limit exceeded
2 Halted 0 ms 0 KB -