#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll,ll> Pll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i, n) for(int i=0;i<n;i++)
#define repp(i, n) for(int i=1;i<=n;i++)
#define all(x) x.begin(), x.end()
#define geti1(X) scanf("%d",&X)
#define geti2(X,Y) scanf("%d%d",&X,&Y)
#define geti3(X,Y,Z) scanf("%d%d%d",&X,&Y,&Z)
#define geti4(X,Y,Z,W) scanf("%d%d%d%d",&X,&Y,&Z,&W)
#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define geti(...) GET_MACRO(__VA_ARGS__, geti4, geti3, geti2, geti1) (__VA_ARGS__)
#define INF 987654321
#define IINF 87654321987654321
#define MAXV 200500
#define MOD 1234567
int N,M,K,T;
vector<int> pos;
vector<Pll> E[60000];
int pa[60000];
bool vis[60000];
set<int> used[60000];
set<Pll> s[60000];
map<Pi,ll> dist;
typedef pair<ll,Pll> ppll;
int main(){
geti(N,M,K,T);
repp(i,K){
int x; geti(x); pos.pb(x);
}
repp(i,M){
ll a,b,c; scanf("%lld%lld%lld",&a,&b,&c);
E[a].push_back({b,c}); E[b].push_back({a,c});
}
priority_queue<ppll, vector<ppll>, greater<ppll>> pq;
for(auto e : pos){
pq.push({0,{e,e}});
pa[e] = e; used[e].insert(e);
s[e].insert({0,e});
}
while(!pq.empty()){
int cur = pq.top().Se.Fi;
int p = pq.top().Se.Se;
ll curd = dist[{cur,p}];
pq.pop();
for(auto e : E[cur]){
if( used[e.Fi].size() >= 11 ) continue;
if( used[e.Fi].find( p ) != used[e.Fi].end() ){
dist[{e.Fi,p}] = min( dist[{e.Fi,p}] , curd + e.Se);
continue;
}
used[e.Fi].insert(p);
dist[{e.Fi,p}] = curd + e.Se;
pq.push({curd+e.Se,{e.Fi,p}});
}
}
/*
repp(i,N){
for(auto e : s[i]){
cout << i << " " << e.Fi << " " << e.Se << endl;
}
}
*/
repp(i,N){
for(auto e : used[i]){
s[i].insert({dist[{i,e}],e});
}
}
//cout << T << endl;
repp(i,T){
int S; geti(S);
int X; geti(X);
set<int> die;
repp(i,X){
int y; geti(y); die.insert(y);
}
//for(auto e : die) printf("[%d]",e);
bool ok = false;
for(auto e : s[S]){
if( die.find(e.Se) == die.end() ){
printf("%lld %lld\n",e.Se,e.Fi);
//printf("!");
ok = true;
break;
}
}
}
}
Compilation message
mart.cpp: In function 'int main()':
mart.cpp:115:8: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
bool ok = false;
^
mart.cpp:55:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
geti(N,M,K,T);
^
mart.cpp:57:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int x; geti(x); pos.pb(x);
^
mart.cpp:61:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
ll a,b,c; scanf("%lld%lld%lld",&a,&b,&c);
^
mart.cpp:108:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int S; geti(S);
^
mart.cpp:109:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int X; geti(X);
^
mart.cpp:112:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int y; geti(y); die.insert(y);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9352 KB |
Output is correct |
| 2 |
Correct |
3 ms |
9352 KB |
Output is correct |
| 3 |
Correct |
0 ms |
9484 KB |
Output is correct |
| 4 |
Correct |
3 ms |
9484 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
9492 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
