#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;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
23 ms |
1856 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
819 ms |
6320 KB |
Output is correct |
