#include<stdio.h>
#include<memory.h>
#include<vector>
#include<queue>
#include<set>
#include<map>
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;
map<pair<int,int>, int> mp;
void edge(int s, int e, int v){
endp[ecn]=e, val[ecn]=v, prv[ecn]=top[s], top[s]=ecn++;
}
int get_dist(int s, int e){
if(mp.find(make_pair(s,e)) == mp.end()) return 2e9;
return mp[make_pair(s,e)];
}
int st, x, close[11], ban[101010];
int main(){
freopen("41","r",stdin);
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));
mp[make_pair(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]){
if(cur.dst+val[i] >= get_dist(cur.st, endp[i])) continue;
mp[make_pair(cur.st, endp[i])] = cur.dst+val[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
mart.cpp: In function 'int main()':
mart.cpp:38:25: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("41","r",stdin);
^
mart.cpp:39: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:43: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:49: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:67: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:68: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;
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
16560 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
