Submission #28381

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
28381	2017-07-16T05:07:40 Z	일단아무거나적어놓은팀이름(#1191, solarmagic, junodeveloper)	Alternative Mart (FXCUP2_mart)	C++14	0 / 1	3 ms	6124 KB

mart

#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
int n, m, k, q;
int martIdx[50001];
priority_queue<pair<ll,int> > d[50001];
vector<pair<ll,int> > dist[50001];
vector<pair<int,ll> > adj[50001];
void dijkstra() {
    priority_queue<pair<ll, pair<int, int> > > q;
    for(int i = 0; i < k; ++i) {
        d[martIdx[i]].push({0, martIdx[i]});
        q.push({0, {martIdx[i], martIdx[i]}});
    }
    while(!q.empty()) {
        int u = q.top().second.first;
        int from = q.top().second.second;
        ll c = -q.top().first; q.pop();
        for(auto& t : adj[u]) {
            int to = t.first;
            ll cost = t.second;
            if(d[to].size() < 11) {
                d[to].push({c + cost, from});
                q.push({-(c + cost), {to, from}});
            } else if(d[to].top().first > c + cost || (d[to].top().first == c + cost && from < d[to].top().second)) {
                d[to].pop();
                d[to].push({c + cost, from});
                q.push({-(c + cost), {to, from}});
            }
        }
    }
}
int main() {
    scanf("%d%d%d%d", &n, &m, &k, &q);
    for(int i = 0; i < k; ++i) scanf("%d", martIdx + i);
    for(int i = 0; i < m; ++i) {
        int a, b, v;
        scanf("%d%d%d", &a, &b, &v);
        adj[a].push_back({b, v});
        adj[b].push_back({a, v});
    }
    dijkstra();
    for(int i = 1; i <= n; ++i) {
        while(!d[i].empty()) {
            dist[i].push_back({d[i].top().first, d[i].top().second});
            d[i].pop();
        }
    }
    for(int i = 0; i < q; ++i) {
        int s, x;
        scanf("%d%d", &s, &x);
        ll mn = 1e18, rIdx = 1e18;
        bool closed[11] = {0};
        for(int j = 0, idx; j < x; ++j) {
            scanf("%d", &idx);
            for(int l = 0; l < dist[s].size(); ++l)
                if(dist[s][l].second == idx) closed[l] = 1;
        }
        for(int j = 0; j < dist[s].size(); ++j) {
            if(closed[j]) continue;
            if(dist[s][j].first < mn || (dist[s][j].first == mn && dist[s][j].second < rIdx)) {
                mn = dist[s][j].first;
                rIdx = dist[s][j].second;
            }
        }
        printf("%lld %lld\n", rIdx, mn);
    }
    return 0;
}

/*
4 5 2 4
1 4
1 2 5
2 4 5
4 3 5
3 1 5
2 3 1
3 0
1 1 1
2 1 4
4 0
*/

Compilation message

mart.cpp: In function 'int main()':
mart.cpp:59:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int l = 0; l < dist[s].size(); ++l)
                              ^
mart.cpp:62:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < dist[s].size(); ++j) {
                          ^
mart.cpp:37:38: 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:38:56: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 0; i < k; ++i) scanf("%d", martIdx + i);
                                                        ^
mart.cpp:41:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &a, &b, &v);
                                    ^
mart.cpp:54:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &s, &x);
                              ^
mart.cpp:58:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &idx);
                              ^

Subtask #1

0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	6124 KB	Output is correct
2	Correct	0 ms	6124 KB	Output is correct
3	Incorrect	3 ms	6124 KB	Output isn't correct
4	Halted	0 ms	0 KB	-