oj.uz

Submission #30929

# Submission time Handle Problem Language Result Execution time Memory
30929 2017-08-01T06:54:32 Z Navick Cities (BOI16_cities) C++14
37 / 100
 4000 ms 36228 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define pii pair<int, int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 1e5 + 10, K = 5;
const ll INF = 1e18;

ll dp[N][1 << K];
vector<pii> adj[N];
int imp[K];
bool see[N];
queue<int> q;

int main(){
	int n, k, m; scanf("%d %d %d", &n, &k, &m);
	for(int i=0; i<k; i++){
		int v; scanf("%d", &v);
		imp[i] = v;
	}

	for(int i=0; i<m; i++){
		int u, v, w; scanf("%d %d %d", &u, &v, &w);
		adj[u].pb({v, w});
		adj[v].pb({u, w});
	}

	for(int mask=1; mask<(1 << k); mask++){
		while(!q.empty())
			q.pop();

		for(int i=1; i<=n; i++){
			dp[i][mask] = INF;
			for(int t=mask; t; t=mask & (t - 1))
				dp[i][mask] = min(dp[i][mask], dp[i][t] + dp[i][mask ^ t]);
			
			q.push(i);
			see[i] = true;
		}

		if(__builtin_popcount(mask) == 1){
			for(int j=0; j<k; j++)
				if(mask & (1 << j))
					dp[imp[j]][mask] = 0;
		}

		while(!q.empty()){
			int v = q.front(); q.pop();
			see[v] = false;
			for(auto X : adj[v]){
				int u = X.F, w = X.S;
				if(dp[u][mask] > dp[v][mask] + w){
					dp[u][mask] = dp[v][mask] + w;
					if(!see[u])
						q.push(u);
				}
			}
		}
	}

	ll res = INF;
	for(int i=1; i<=n; i++)
		res = min(res, dp[i][(1 << k) - 1]);
	printf("%lld\n", res);
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:22:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, k, m; scanf("%d %d %d", &n, &k, &m);
                                            ^
cities.cpp:24:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int v; scanf("%d", &v);
                         ^
cities.cpp:29:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v, w; scanf("%d %d %d", &u, &v, &w);
                                             ^

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 29468 KB Output is correct
2 Correct 0 ms 29468 KB Output is correct
3 Correct 0 ms 29468 KB Output is correct
4 Correct 0 ms 29468 KB Output is correct
5 Correct 0 ms 29468 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 743 ms 36140 KB Output is correct
2 Correct 553 ms 36228 KB Output is correct
3 Execution timed out 4000 ms 33036 KB Execution timed out
4 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 29600 KB Output is correct
2 Correct 0 ms 29600 KB Output is correct
3 Correct 9 ms 29468 KB Output is correct
4 Correct 3 ms 29600 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1216 ms 36180 KB Output is correct
2 Correct 979 ms 36024 KB Output is correct
3 Execution timed out 4000 ms 33036 KB Execution timed out
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2456 ms 36132 KB Output is correct
2 Correct 2833 ms 36128 KB Output is correct
3 Correct 1866 ms 36068 KB Output is correct
4 Execution timed out 4000 ms 33036 KB Execution timed out
5 Halted 0 ms 0 KB -