oj.uz

Submission #53063

# Submission time Handle Problem Language Result Execution time Memory
53063 2018-06-28T00:24:44 Z andremfq Cities (BOI16_cities) C++17
100 / 100
 1297 ms 89304 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <time.h>
#include <iostream>
#include <functional>
#include <numeric>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <bitset>
#include <map>
#include <set>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<lint, int> pi;

lint ret = 1e18;
priority_queue<pi, vector<pi>, greater<pi> > pq;
vector<pi> gph[100005];

int n, m, k, a[10];
lint dist[6][100005];
lint dt[6][6][100005];

void getdt(int s, int e){
	for(int i=1; i<=n; i++){
		pq.push(pi(dist[s][i] + dist[e][i], i));
		dt[s][e][i] = dist[s][i] + dist[e][i];
	}
	while(!pq.empty()){
		auto t = pq.top();
		pq.pop();
		if(dt[s][e][t.second] < t.first) continue;
		for(auto &i : gph[t.second]){
			if(dt[s][e][i.second] > dt[s][e][t.second] + i.first){
				dt[s][e][i.second] = dt[s][e][t.second] + i.first;
				pq.push(pi(dt[s][e][i.second], i.second));
			}
		}
	}

}

void dijkstra(vector<int> &start, lint *d){
	for(auto &i : start){
		d[i] = 0;
		pq.push(pi(0, i));
	}
	while(!pq.empty()){
		auto t = pq.top();
		pq.pop();
		if(d[t.second] < t.first) continue;
		for(auto &i : gph[t.second]){
			if(d[i.second] > d[t.second] + i.first){
				d[i.second] = d[t.second] + i.first;
				pq.push(pi(d[i.second], i.second));
			}
		}
	}
}

lint solve1(int *p){
	lint ret = 1e18;
	for(int i=1; i<=n; i++){
		ret = min(ret, dt[p[0]][p[1]][i] + dt[p[2]][p[3]][i]);
	}
	return ret;
}

lint solve2(int *p){
	lint ret = 1e18;
	for(int i=1; i<=n; i++){
		ret = min(ret, dt[p[0]][p[1]][i] + dt[p[2]][p[3]][i] + dist[p[4]][i]);
	}
	return ret;
}

int main(){
	cin >> n >> k >> m;
	for(int i=1; i<=k; i++) cin >> a[i];
	sort(a+1, a+k+1);
	k = unique(a+1, a+k+1) - a - 1;
	for(int i=1; i<=m; i++){
		int s, e, x;
		scanf("%d %d %d",&s,&e,&x);
		gph[s].emplace_back(x, e);
		gph[e].emplace_back(x, s);
	}
	memset(dist, 0x3f, sizeof(dist));
	for(int i=1; i<=k; i++){
		vector<int> t;
		t.push_back(a[i]);
		dijkstra(t, dist[i]);
	}
	if(k == 1){
		puts("0");
		return 0;
	}
	if(k == 2){
		printf("%lld\n",dist[1][a[2]]);
		return 0;
	}
	if(k == 3){
		for(int i=1; i<=n; i++){
			ret = min(ret, dist[1][i] + dist[2][i] + dist[3][i]);
		}
		printf("%lld\n",ret);
		return 0;
	}
	if(k == 4){
		for(int i=1; i<=k; i++){
			for(int j=i+1; j<=k; j++){
				getdt(i, j);
			}
		}
		int perm[4] = {1, 2, 3, 4};
		do{
			if(perm[0] < perm[1] && perm[2] < perm[3] && perm[0] < perm[2]){
				ret = min(ret, solve1(perm));
			}
		}while(next_permutation(perm, perm + 4));
		printf("%lld", ret);
		return 0;
	}
	if(k == 5){
		for(int i=1; i<=k; i++){
			for(int j=i+1; j<=k; j++){
				getdt(i, j);
			}
		}
		int perm[5] = {1, 2, 3, 4, 5};
		do{
			if(perm[0] < perm[1] && perm[2] < perm[3] && perm[0] < perm[2]){
				ret = min(ret, solve2(perm));
			}
		}while(next_permutation(perm, perm + 5));
		printf("%lld", ret);
		return 0;
	}
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&s,&e,&x);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7416 KB Output is correct
2 Correct 7 ms 7472 KB Output is correct
3 Correct 7 ms 7520 KB Output is correct
4 Correct 7 ms 7584 KB Output is correct
5 Correct 9 ms 7788 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 23508 KB Output is correct
2 Correct 310 ms 27912 KB Output is correct
3 Correct 142 ms 27912 KB Output is correct
4 Correct 106 ms 30892 KB Output is correct
5 Correct 280 ms 37656 KB Output is correct
6 Correct 141 ms 38572 KB Output is correct
7 Correct 11 ms 38572 KB Output is correct
8 Correct 9 ms 38572 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 38572 KB Output is correct
2 Correct 11 ms 38572 KB Output is correct
3 Correct 9 ms 38572 KB Output is correct
4 Correct 10 ms 38572 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 842 ms 51540 KB Output is correct
2 Correct 790 ms 55216 KB Output is correct
3 Correct 511 ms 55216 KB Output is correct
4 Correct 510 ms 58904 KB Output is correct
5 Correct 199 ms 58904 KB Output is correct
6 Correct 112 ms 63080 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1184 ms 77040 KB Output is correct
2 Correct 1297 ms 81188 KB Output is correct
3 Correct 1180 ms 84700 KB Output is correct
4 Correct 733 ms 84700 KB Output is correct
5 Correct 810 ms 86736 KB Output is correct
6 Correct 248 ms 86736 KB Output is correct
7 Correct 119 ms 89304 KB Output is correct