Submission #29130

#	Time	Username	Problem	Language	Result	Execution time	Memory
29130		jjwdi0	Alternative Mart (FXCUP2_mart)	C++11	1 / 1	1743 ms	61808 KiB

mart

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Z { int x, y, c; } T[80003];
struct Q {
    int x, st;
    ll c;
    Q(int _x, int _st, ll _c) { x = _x, st = _st, c = _c; }
    bool operator < (const Q &A) const { return c == A.c ? st < A.st : c < A.c; }
    bool operator > (const Q &A) const { return c == A.c ? st > A.st : c > A.c; }
};

int N, M, K, _Q;
vector<int> v[50003];
bool mart[50003];
ll D[50003][12];
int num[50003][12], idx[50003];
int q[13];
priority_queue<Q, vector<Q>, greater<Q>> pq;

int main() {
    scanf("%d %d %d %d", &N, &M, &K, &_Q);
    for(int i=0, x; i<K; i++) scanf("%d", &x), mart[x] = 1;
    for(int i=0; i<M; i++) {
        scanf("%d %d %d", &T[i].x, &T[i].y, &T[i].c);
        v[T[i].x].push_back(i);
        v[T[i].y].push_back(i);
    }
    for(int i=1; i<=N; i++) for(int j=1; j<=11; j++) D[i][j] = 1e15;
    for(int i=1; i<=N; idx[i] = 1, i++) if(mart[i]) pq.push(Q(i, i, 0));
    while(!pq.empty()) {
        int u = pq.top().x, st = pq.top().st; ll cost = pq.top().c; pq.pop();
        int id = idx[u];
        if(id > 11) continue;
        bool chk = 0;
        for(int i=1; i<=id; i++) if(num[u][i] == st) chk = 1;
        if(chk) continue;
        num[u][id] = st, idx[u]++, D[u][id] = cost;
        for(int it : v[u]) {
            int ne = T[it].x == u ? T[it].y : T[it].x;
            ll c = T[it].c;
            pq.push(Q(ne, st, c + cost));
        }
    }
    for(int i=0; i<_Q; i++) {
        int s, x;
        scanf("%d %d", &s, &x);
        for(int j=0; j<x; j++) scanf("%d", q+j);
        for(int j=1; j<=11; j++) {
            bool chk = 0;
            for(int k=0; k<x; k++) if(q[k] == num[s][j]) chk = 1;
            if(chk == 0) { printf("%d %lld\n", num[s][j], D[s][j]); break; }
        }
    }
}

Compilation message (stderr)

mart.cpp: In function 'int main()':
mart.cpp:23:42: 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:24:59: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=0, x; i<K; i++) scanf("%d", &x), mart[x] = 1;
                                                           ^
mart.cpp:26:53: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &T[i].x, &T[i].y, &T[i].c);
                                                     ^
mart.cpp:48:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &s, &x);
                               ^
mart.cpp:49:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         for(int j=0; j<x; j++) scanf("%d", q+j);
                                                ^

• Subtask 1: 1 / 1