| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 28998 | 2017-07-18T04:56:10 Z | TAMREF | Alternative Mart (FXCUP2_mart) | C++11 | 816 ms | 19996 KB |
#include <bits/stdc++.h>
#define va first
#define vb second
#define mp make_pair
#define all(x) x.begin(),x.end()
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,int> pt;
const int mx=50005, inf=1e9;
int N,M,K,Q;
vector<pii> G[mx];
pii dist[mx][12];
int hi[mx];
void input(){
scanf("%d%d%d%d",&N,&M,&K,&Q);
for(int i=0;i<K;i++){
scanf("%d",&hi[i]);
}
for(int i=0,a,b,c;i<M;i++){
scanf("%d%d%d",&a,&b,&c);
G[a].push_back(mp(b,c));
G[b].push_back(mp(a,c));
}
for(int i=0;i<mx;i++) fill(dist[i],dist[i]+11,mp(inf,0));
}
void dijk(){
priority_queue<pt,vector<pt>,greater<pt>> q;
for(int i=0;i<K;i++){
dist[hi[i]][0]=mp(0,hi[i]);
q.push(mp(dist[hi[i]][0],hi[i]));
}
pt u;
int rodong;
while(!q.empty()){
u=q.top(); q.pop(); //u.va.va : cost, u.va.vb : source
int p;
if(dist[u.vb][10]<u.va) continue;
for(pii x : G[u.vb]){ //x.va : vertex, x.vb : cost
for(p=0;p<11;p++){
if(dist[x.va][p].vb==u.va.vb){
if(dist[x.va][p].va>u.va.va+x.vb){
dist[x.va][p].va=u.va.va+x.vb;
q.push(mp(dist[x.va][p],x.va));
sort(dist[x.va],dist[x.va]+11);
}
goto term;
}
}
for(p=11;p;p--) dist[x.va][p]=dist[x.va][p-1];
for(int p=1;p<=11;p++){
if(dist[x.va][p]>mp(u.va.va+x.vb,u.va.vb)){
dist[x.va][p-1]=mp(u.va.va+x.vb,u.va.vb);
q.push(mp(dist[x.va][p-1],x.va));
break;
}else{
dist[x.va][p-1]=dist[x.va][p];
}
}
term:
rodong=rodong;
}
}
}
void debug(){
for(int i=1;i<=N;i++){
for(int j=0;j<11;j++){
printf("(%d from %d) ",dist[i][j].va==inf?-1:dist[i][j].va,dist[i][j].vb);
} puts("");
}
}
void query(){
int X,S,v;
unordered_set<int> u;
for(;Q--;){
u.clear();
scanf("%d%d",&S,&X);
for(int i=0;i<X;i++){
scanf("%d",&v);
u.insert(v);
}
for(int i=0;i<11;i++){
if(u.find(dist[S][i].vb)==u.end()){
printf("%d %d\n",dist[S][i].vb,dist[S][i].va);
break;
}
}
}
}
int main(){
//freopen("input.txt","rt",stdin);
input();
dijk();
//debug();
query();
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 3 ms | 8084 KB | Output is correct |
| 2 | Correct | 0 ms | 8084 KB | Output is correct |
| 3 | Correct | 3 ms | 8084 KB | Output is correct |
| 4 | Correct | 3 ms | 8084 KB | Output is correct |
| 5 | Correct | 6 ms | 8084 KB | Output is correct |
| 6 | Correct | 3 ms | 8084 KB | Output is correct |
| 7 | Correct | 3 ms | 8228 KB | Output is correct |
| 8 | Correct | 3 ms | 8084 KB | Output is correct |
| 9 | Correct | 23 ms | 8840 KB | Output is correct |
| 10 | Correct | 13 ms | 8832 KB | Output is correct |
| 11 | Correct | 29 ms | 8540 KB | Output is correct |
| 12 | Correct | 19 ms | 8216 KB | Output is correct |
| 13 | Correct | 199 ms | 14996 KB | Output is correct |
| 14 | Correct | 173 ms | 15000 KB | Output is correct |
| 15 | Correct | 89 ms | 10220 KB | Output is correct |
| 16 | Correct | 93 ms | 9668 KB | Output is correct |
| 17 | Correct | 456 ms | 11188 KB | Output is correct |
| 18 | Correct | 336 ms | 9668 KB | Output is correct |
| 19 | Correct | 449 ms | 12344 KB | Output is correct |
| 20 | Correct | 369 ms | 9668 KB | Output is correct |
| 21 | Correct | 453 ms | 12340 KB | Output is correct |
| 22 | Correct | 339 ms | 9820 KB | Output is correct |
| 23 | Correct | 486 ms | 14644 KB | Output is correct |
| 24 | Correct | 519 ms | 12036 KB | Output is correct |
| 25 | Correct | 549 ms | 14644 KB | Output is correct |
| 26 | Correct | 506 ms | 12036 KB | Output is correct |
| 27 | Correct | 109 ms | 10660 KB | Output is correct |
| 28 | Correct | 103 ms | 10364 KB | Output is correct |
| 29 | Correct | 566 ms | 12668 KB | Output is correct |
| 30 | Correct | 486 ms | 11152 KB | Output is correct |
| 31 | Correct | 613 ms | 14808 KB | Output is correct |
| 32 | Correct | 466 ms | 11040 KB | Output is correct |
| 33 | Correct | 566 ms | 12420 KB | Output is correct |
| 34 | Correct | 643 ms | 15104 KB | Output is correct |
| 35 | Correct | 573 ms | 14804 KB | Output is correct |
| 36 | Correct | 639 ms | 14940 KB | Output is correct |
| 37 | Correct | 653 ms | 19728 KB | Output is correct |
| 38 | Correct | 626 ms | 15036 KB | Output is correct |
| 39 | Correct | 139 ms | 11348 KB | Output is correct |
| 40 | Correct | 143 ms | 11348 KB | Output is correct |
| 41 | Correct | 593 ms | 15376 KB | Output is correct |
| 42 | Correct | 633 ms | 15384 KB | Output is correct |
| 43 | Correct | 693 ms | 15380 KB | Output is correct |
| 44 | Correct | 553 ms | 15384 KB | Output is correct |
| 45 | Correct | 739 ms | 15380 KB | Output is correct |
| 46 | Correct | 669 ms | 15388 KB | Output is correct |
| 47 | Correct | 713 ms | 19984 KB | Output is correct |
| 48 | Correct | 816 ms | 19988 KB | Output is correct |
| 49 | Correct | 703 ms | 19988 KB | Output is correct |
| 50 | Correct | 629 ms | 19996 KB | Output is correct |
| 51 | Correct | 609 ms | 19980 KB | Output is correct |
| 52 | Correct | 593 ms | 19988 KB | Output is correct |
| 53 | Correct | 306 ms | 9668 KB | Output is correct |
| 54 | Correct | 589 ms | 15076 KB | Output is correct |
| 55 | Correct | 719 ms | 15048 KB | Output is correct |
| 56 | Correct | 773 ms | 15380 KB | Output is correct |
| 57 | Correct | 159 ms | 12336 KB | Output is correct |