oj.uz

Submission #1010364

# Submission time Handle Problem Language Result Execution time Memory
1010364 2024-06-29T01:15:03 Z uyt777443 Cities (BOI16_cities) C++17
14 / 100
 275 ms 46388 KB 
// https://oj.uz/problem/view/BOI16_cities

#include <iostream>
#include <iomanip>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <vector>
#include <utility>
#include <algorithm>
#include <numeric>
#include <string>
#include <cmath>
#include <random>
#include <sstream>
#include <string.h>
#include <assert.h>
#include <limits.h>
using namespace std;

#define fi first
#define se second
#define int long long
#define pb push_back

typedef pair<int,int> ii;

const int INF = 1e18;

vector<vector<ii> > adj(100000 + 2);
vector<int> sp;
int dp[100000 + 2][32 + 2];

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, k, m; cin >> n >> k >> m;
	for (int i=1; i<=k; i++) {
		int a; cin >> a; sp.pb(a);
	}
	for (int i=1; i<=m; i++) {
		int a, b, c; cin >> a >> b >> c; adj[a].pb({b, c}); adj[b].pb({a, c});
	}

	for (int i=1; i<=n; i++) for (int j=1; j<=32; j++) dp[i][j] = INF;

  
	for (int mask = 1; mask <= (1 << k) - 1; mask++) {
    	for (int i=0; i<5; i++) {
			if (mask & (1 << i)) {
				for (int j=1; j<=n; j++) 
					dp[j][mask] = dp[j][mask - (1 << i)] + dp[j][(1 << i)];
			}
		}
		
		priority_queue<ii, vector<ii>, greater<ii> > pq;
        for (int i=0; i<5; i++) {
            if (mask & (1 << i)) {
                dp[sp[i]][(1 << i)] = 0;
                pq.push({dp[sp[i]][mask], sp[i]}); 
            }
        }
		while(!pq.empty()) {
			ii cur = pq.top(); pq.pop();
			int des = cur.se, dis = cur.fi;
			for (auto nx : adj[des]) {
				int ndes = nx.fi, w = nx.se;
                int nxmask = mask;
				for (int i=0; i<5; i++) {
					if (ndes == sp[i]) nxmask += (1 << i);
				}
				if (dp[ndes][nxmask] <= dp[des][mask] + w) continue;
                dp[ndes][nxmask] = dp[des][nxmask] + w;
                pq.push({dp[ndes][nxmask], ndes});
			}
		}
	}

	int ans = INF;
	for (int i=1; i<=n; i++) {
		ans = min(ans, dp[i][(1 << k) - 1]);
	} cout << ans;
	
	return 0;
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:67:22: warning: unused variable 'dis' [-Wunused-variable]
   67 |    int des = cur.se, dis = cur.fi;
      |                      ^~~

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Incorrect 1 ms 2652 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 45668 KB Output is correct
2 Correct 170 ms 46388 KB Output is correct
3 Correct 70 ms 36692 KB Output is correct
4 Correct 116 ms 15600 KB Output is correct
5 Correct 140 ms 45676 KB Output is correct
6 Correct 101 ms 15592 KB Output is correct
7 Correct 2 ms 3160 KB Output is correct
8 Correct 2 ms 3160 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 26.0

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