Submission #28708

#TimeUsernameProblemLanguageResultExecution timeMemory
28708슈퍼스타 tlwpdus (#68)Alternative Mart (FXCUP2_mart)C++11
0 / 1
5000 ms163924 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> pii; int n, m, k, q; vector<int> mart; vector<pii> lis[50010]; map<pii,int> fin; pii rin[3000000]; int p; int dis[3000000]; int cnt[50010]; vector<pii> gd[50010]; int msv = 15; void dijk() { int i; priority_queue<pii> pq; for (i=0;i<3000000;i++) dis[i] = 987654321; for (i=0;i<k;i++) { fin[pii(mart[i],mart[i])] = p; rin[p] = pii(mart[i],mart[i]); dis[p] = 0; pq.push(pii(0,p)); p++; } while(!pq.empty()) { pii tmp = pq.top(); pq.pop(); if (dis[tmp.second]!=-tmp.first||cnt[rin[tmp.second].first]>=msv) continue; int here = rin[tmp.second].first, mar = rin[tmp.second].second, d = -tmp.first; cnt[here]++; for (auto &tmp : lis[here]) { int there = tmp.second, w = tmp.first; if (cnt[there]>=msv) continue; auto it = fin.find(pii(there,mar)); int curp; if (it==fin.end()) { curp = p; fin[pii(there,mar)] = p; rin[p] = pii(there,mar); p++; } else curp = it->second; if (dis[curp]<=d+w) continue; dis[curp] = d+w; pq.push(pii(-d-w,curp)); } } for (i=0;i<p;i++) gd[rin[i].first].push_back(pii(dis[i],rin[i].second)); for (i=0;i<n;i++) sort(gd[i].begin(),gd[i].end()); } vector<int> que; bool qchk[50010]; int main() { int i, j; scanf("%d%d%d%d",&n,&m,&k,&q); for (i=0;i<k;i++) { int a; scanf("%d",&a); --a; mart.push_back(a); } for (i=0;i<m;i++) { int a, b, c; scanf("%d%d%d",&a,&b,&c); --a; --b; lis[a].push_back(pii(c,b)); lis[b].push_back(pii(c,a)); } dijk(); que.reserve(12); for (i=0;i<q;i++) { int s, x; scanf("%d%d",&s,&x); --s; for (int j=0;j<x;j++) { int a; scanf("%d",&a); --a; que.push_back(a); qchk[a] = 1; } for (j=0;j<gd[s].size();j++) { if (!qchk[gd[s][j].second]) { printf("%d %d\n",gd[s][j].second+1,gd[s][j].first); break; } } for (int j=0;j<x;j++) { qchk[que[j]] = 0; } que.clear(); } return 0; }

Compilation message (stderr)

mart.cpp: In function 'int main()':
mart.cpp:87:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (j=0;j<gd[s].size();j++) {
             ^
mart.cpp:64:31: 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:67:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a); --a;
                 ^
mart.cpp:72:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&a,&b,&c); --a; --b;
                           ^
mart.cpp:80:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&s,&x); --s;
                      ^
mart.cpp:83:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&a); --a;
                  ^
#Verdict Execution timeMemoryGrader output
Fetching results...