Submission #13824

#	Time	Username	Problem	Language	Result	Execution time	Memory
13824		veckal	약속장소 정하기 (GCJ12KOR_appointment)	C++14	35 / 35	819 ms	6320 KiB

C

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int, int> ii;
const int INF = 987654321;

int n, p, m, x[100], v[100];
vector<ii> adj[10000];
int dist[10000];

int main() {
	int T;
	scanf("%d", &T);
	for (int N=1; N<=T; ++N) {
		for (int i=0; i<10000; ++i)
			adj[i].clear();
		scanf("%d%d%d", &n, &p, &m);
		for (int i=0; i<p; ++i) {
			scanf("%d%d", x+i, v+i);
			--x[i];
		}
		for (int i=0; i<m; ++i) {
			int d, l, c, nc;
			scanf("%d%d%d", &d, &l, &c);
			--c;
			while (--l) {
				scanf("%d", &nc);
				--nc;
				adj[c].emplace_back(nc, d);
				adj[nc].emplace_back(c, d);
				c = nc;
			}
		}
		memset(dist, 0, sizeof dist);
		for (int i=0; i<p; ++i) {
			priority_queue<ii> pq;
			vector<int> d(n, INF);
			vector<bool> visited(n);
			pq.emplace(0, x[i]);
			d[x[i]] = 0;
			while (!pq.empty()) {
				int here = pq.top().second;
				int dist = -pq.top().first;
				pq.pop();
				if (visited[here]) continue;
				visited[here] = true;
				for (ii &nd : adj[here]) {
					int next = nd.first, ndist = dist + nd.second;
					if (visited[next] || ndist >= d[next]) continue;
					pq.emplace(-ndist, next);
					d[next] = ndist;
				}
			}
			for (int j=0; j<n; ++j) {
				if (visited[j])
					dist[j] = max(dist[j], d[j]*v[i]);
				else
					dist[j] = INF;
			}
		}
		int ans = *min_element(dist, dist+n);
		if (ans == INF) ans = -1;
		printf("Case #%d: ", N);
		printf("%d\n", ans);
	}
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25