Submission #26997

#TimeUsernameProblemLanguageResultExecution timeMemory
26997imsifileAlternative Mart (FXCUP2_mart)C++98
1 / 1
3553 ms55100 KiB
#include<stdio.h> #include<memory.h> #include<vector> #include<queue> #include<set> using namespace std; struct nod { int st, ix, dst; nod(int st_, int ix_, int dst_){ st=st_, ix=ix_, dst=dst_; } bool operator< (const nod& c) const { if(dst != c.dst) return dst > c.dst; return st > c.st; } }; priority_queue<nod> pq; int N, M, K, Q; int endp[406060], val[406060], prv[406060], top[101010], ecn; int dist[101010][11], dnum[101010][11], dcn[101010]; set<pair<int,int> > chk; void edge(int s, int e, int v){ endp[ecn]=e, val[ecn]=v, prv[ecn]=top[s], top[s]=ecn++; } int st, x, close[11], ban[101010]; int main(){ scanf("%d%d%d%d", &N, &M, &K, &Q); for(int i=1; i<=N; i++) top[i]=-1; memset(dist, 0x3f, sizeof(dist)); for(int i=K; i--;){ int a; scanf("%d", &a); pq.push(nod(a, a, 0)); } for(int i=M; i--;){ int s, e, v; scanf("%d%d%d", &s, &e, &v); edge(s, e, v), edge(e, s, v); } while(!pq.empty()){ nod cur = pq.top(); pq.pop(); if(dcn[cur.ix] >= 11) continue; if(chk.find(make_pair(cur.ix, cur.st)) != chk.end()) continue; int dix = dcn[cur.ix]; dist[cur.ix][dix] = cur.dst, dnum[cur.ix][dix] = cur.st, dcn[cur.ix]++; chk.insert(make_pair(cur.ix, cur.st)); for(int i=top[cur.ix]; i>=0; i=prv[i]) pq.push(nod(cur.st, endp[i], cur.dst+val[i])); } for(int t=Q; t--;){ scanf("%d%d", &st, &x); for(int i=0; i<x; i++) scanf("%d", &close[i]), ban[close[i]]=1; for(int i=0; i<=10; i++){ if(ban[dnum[st][i]]) continue; printf("%d %d\n", dnum[st][i], dist[st][i]); break; } for(int i=0; i<x; i++) ban[close[i]]=0; } return 0; }

Compilation message (stderr)

mart.cpp: In function 'int main()':
mart.cpp:31:35: 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:35:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a; scanf("%d", &a);
                         ^
mart.cpp:40:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &s, &e, &v);
                              ^
mart.cpp:54:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &st, &x);
                         ^
mart.cpp:55:65: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(int i=0; i<x; i++) scanf("%d", &close[i]), ban[close[i]]=1;
                                                                 ^
#Verdict Execution timeMemoryGrader output
Fetching results...