oj.uz

Submission #28393

# Submission time Handle Problem Language Result Execution time Memory
28393 2017-07-16T05:14:30 Z 일단아무거나적어놓은팀이름(#1191, solarmagic, junodeveloper) Alternative Mart (FXCUP2_mart) C++14
0 / 1
 3 ms 8472 KB 
#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<set>
using namespace std;
typedef long long ll;
int n, m, k, q;
int martIdx[50001];
priority_queue<pair<ll,int> > d[50001];
set<int> visited[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]});
        visited[martIdx[i]].insert(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(visited[to].find(from) != visited[to].end()) continue;
            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:63:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int l = 0; l < dist[s].size(); ++l)
                              ^
mart.cpp:66:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < dist[s].size(); ++j) {
                          ^
mart.cpp:41: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:42: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:45: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:58: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:62: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 0 ms 8472 KB Output is correct
2 Correct 3 ms 8472 KB Output is correct
3 Incorrect 3 ms 8472 KB Output isn't correct
4 Halted 0 ms 0 KB -