oj.uz

답안 #670956

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
670956 2022-12-11T13:49:14 Z dozer Cities (BOI16_cities) C++14
0 / 100
 6000 ms 2644 KB 
#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define sp " "
#define endl "\n"
#define pii pair<int, int>
#define st first
#define nd second
#define N 100005
#define M 40
#define int long long

int arr[N], dist[N][M], flag[N];
pii ind[N * M];
int rev[N][M];
vector<pii> adj[N];

const int INF = 1e18 + 7;

int32_t main()
{
	#ifndef ONLINE_JUDGE
	fileio();
	#endif
	fastio();

 	int n, m, k;
 	cin>>n>>k>>m;
 	for (int i = 1; i <= k; i++)
 	{
 		int node;
 		cin>>node;
 		flag[node] = 1;
 		arr[node] = i - 1;
 	}

 	for (int i = 1; i <= m; i++)
 	{
 		int u, v, w;
 		cin>>u>>v>>w;
 		adj[u].pb({v, w});
 		adj[v].pb({u, w});
 	}

 	int cntr = 1;
 	for (int i = 1; i <= n; i++) 
 	{
 		for (int j = 0; j < (1<<k); j++) 
 		{
 			dist[i][j] = INF;
 			ind[cntr] = {i, j};
 			rev[i][j] = cntr;
 			cntr++;
 		}
 	}

 	priority_queue<pii> q;
 	for (int i = 1; i <= n; i++)
 	{
 		if (flag[i]) 
 		{
 			q.push({0, rev[i][(1<<arr[i])]});
 			dist[i][(1<<arr[i])] = 0;
 		}
 	}

 	int steps = 0;
 	while(!q.empty())
 	{
 		pii tmp = q.top();
 		q.pop();
 		int x = tmp.nd;
 		int top = ind[x].st, mask = ind[x].nd, d = -tmp.st;
 		if (d != dist[top][mask]) continue;
 		int comp = ((1<<k) - 1) ^ mask;
 		for (auto i : adj[top])
 		{
 			int v = i.st, w = i.nd;
 			int tmpo = 0;
 			for (int j = comp; j > 0; j = (j - 1) & comp)
 			{
 				steps++;
 				tmpo++;
 				int gh = mask | j;
 				if (dist[v][gh] > w + d + dist[v][j])
 				{
 					dist[v][gh] = w + d + dist[v][j];
 					q.push({-dist[v][gh], rev[v][gh]});
 				}
 			}
 			int gh = mask;
 			if (dist[v][gh] > w + d)
			{
				dist[v][gh] = w + d;
				q.push({-dist[v][gh], rev[v][gh]});
			}
 		}
 	}
 	int ans = INF;
 	for (int i = 1; i <= n; i++)
 	{
 		ans = min(ans, dist[i][(1<<k) - 1]);
 	}
 	cout<<ans<<endl;
	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

Compilation message

cities.cpp: In function 'int32_t main()':
cities.cpp:3:25: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
      |                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:25:2: note: in expansion of macro 'fileio'
   25 |  fileio();
      |  ^~~~~~
cities.cpp:3:59: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
      |                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:25:2: note: in expansion of macro 'fileio'
   25 |  fileio();
      |  ^~~~~~

Subtask #1
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6079 ms 2644 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6058 ms 2644 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6099 ms 2644 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6033 ms 2644 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6014 ms 2644 KB Time limit exceeded
2 Halted 0 ms 0 KB -