Submission #28998

#	Time	Username	Problem	Language	Result	Execution time	Memory
28998		TAMREF	Alternative Mart (FXCUP2_mart)	C++11	1 / 1	816 ms	19996 KiB

mart

#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 (stderr)

mart.cpp: In function 'void input()':
mart.cpp:15:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d",&N,&M,&K,&Q);
                                  ^
mart.cpp:17:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&hi[i]);
                           ^
mart.cpp:20:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&a,&b,&c);
                                 ^
mart.cpp: In function 'void query()':
mart.cpp:76:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&S,&X);
                            ^
mart.cpp:78:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&v);
                           ^

• Subtask 1: 1 / 1