#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int,int> pi;
int cand[10005][105];
int cnt[10005];
vector<pi> graph[10005];
int n, p, m;
int st[105], vel[105];
bool vis[10005];
void solve(){
scanf("%d %d %d",&n,&p,&m);
for (int i=1; i<=n; i++) {
graph[i].clear();
}
memset(cand,0x3f,sizeof(cand));
memset(cnt,0,sizeof(cnt));
for (int i=1; i<=p; i++) {
scanf("%d %d",&st[i],&vel[i]);
}
for (int i=0; i<m; i++) {
int d, t, s;
scanf("%d %d %d",&d,&t,&s);
for (int j=1; j<t; j++) {
int u;
scanf("%d",&u);
graph[s].push_back(pi(d,u));
graph[u].push_back(pi(d,s));
s = u;
}
}
priority_queue<pi,vector<pi>,greater<pi> > pq;
for (int i=1; i<=p; i++) {
memset(vis,0,sizeof(vis));
pq.push(pi(0,st[i]));
while (!pq.empty()) {
pi t = pq.top();
pq.pop();
if(vis[t.second]) continue;
vis[t.second] = 1;
cand[t.second][i] = t.first * vel[i];
cnt[t.second]++;
for (auto &j : graph[t.second]){
if(vis[j.second]) continue;
if(cand[j.second][i] < t.first + j.first) continue;
cand[j.second][i] = j.first + t.first;
pq.push(pi(j.first + t.first,j.second));
}
}
}
int pos = -1, posv = 1e9;
for (int i=1; i<=n; i++) {
if(cnt[i] != p) continue;
int mv = *max_element(cand[i] + 1,cand[i] + p + 1);
if(posv > mv) {
posv = mv;
pos = i;
}
}
if(pos == -1) posv = -1;
printf("%d",posv);
}
int main(){
int t;
scanf("%d",&t);
for (int i=1; i<=t; i++) {
printf("Case #%d: ",i);
solve();
puts("");
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
5600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
905 ms |
9908 KB |
Output is correct |
