Submission #151784

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
151784	2019-09-04T17:10:17 Z	gs18065	Alternative Mart (FXCUP2_mart)	C++14	1 / 1	1936 ms	75036 KB

mart

#include <bits/stdc++.h>
#define N 50005
#define M 1000003
#define INF 2000000009
#define LINF 9000000000000000009LL
#define fi first
#define se second
#define eb emplace_back
#define lb lower_bound
#define all(x) (x).begin(),(x).end()
#define uniqv(x) (x).erase(unique(all(x)),(x).end())
#define fastio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> tri;

int n,m,k,q,s[N],cnt;
vector<pll> net[N];
vector<pll> dist[N];
set<int> vis[N];

void dijkstra(){
	priority_queue<tri,vector<tri>,greater<tri> > Q;
	for(int i=0;i<k;i++){
		Q.push({0,{s[i],s[i]}});
	}
	while(!Q.empty()){
		tri p=Q.top();
		Q.pop();
		int now=p.se.se,from=p.se.fi;
		ll cost=p.fi;
		if(vis[now].size()==11||vis[now].find(from)!=vis[now].end()) continue;
		vis[now].insert(from);
		dist[now].eb(cost,from);
		for(auto i:net[now]){
			int next=i.fi;
			ll nextcost=cost+i.se;
			Q.push({nextcost,{from,next}});
		}
	}
	return;
}
int main(){
	fastio;
	cin>>n>>m>>k>>q;
	for(int i=0;i<k;i++){
		cin>>s[i];
	}
	for(int i=0,t1,t2;i<m;i++){
		ll val;
		cin>>t1>>t2>>val;
		net[t1].eb(t2,val);
		net[t2].eb(t1,val);
	}	
	dijkstra();
	while(q--){
		int st,num;
		cin>>st>>num;
		vector<bool> chk(n+1,false);
		for(int i=0,t;i<num;i++){
			cin>>t;
			chk[t]=true;
		}
		ll ans1=LINF,ans2=LINF;
		for(int i=0;i<dist[st].size();i++){
			if(chk[dist[st][i].se]) continue;
			if(dist[st][i].fi<ans2||(dist[st][i].fi==ans2&&dist[st][i].se<ans1)){
				ans1=dist[st][i].se;
				ans2=dist[st][i].fi;
			}
		}
		cout<<ans1<<" "<<ans2<<"\n";
	}
	return 0;
}

Compilation message

mart.cpp: In function 'int main()':
mart.cpp:67:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<dist[st].size();i++){
               ~^~~~~~~~~~~~~~~~

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	4984 KB	Output is correct
2	Correct	7 ms	4948 KB	Output is correct
3	Correct	6 ms	5112 KB	Output is correct
4	Correct	6 ms	4984 KB	Output is correct
5	Correct	7 ms	5112 KB	Output is correct
6	Correct	7 ms	5160 KB	Output is correct
7	Correct	10 ms	5496 KB	Output is correct
8	Correct	10 ms	5496 KB	Output is correct
9	Correct	98 ms	11880 KB	Output is correct
10	Correct	82 ms	12260 KB	Output is correct
11	Correct	68 ms	9912 KB	Output is correct
12	Correct	55 ms	9592 KB	Output is correct
13	Correct	965 ms	61804 KB	Output is correct
14	Correct	968 ms	61956 KB	Output is correct
15	Correct	138 ms	13300 KB	Output is correct
16	Correct	120 ms	13376 KB	Output is correct
17	Correct	1086 ms	47936 KB	Output is correct
18	Correct	746 ms	48760 KB	Output is correct
19	Correct	1242 ms	51504 KB	Output is correct
20	Correct	903 ms	51116 KB	Output is correct
21	Correct	1089 ms	52276 KB	Output is correct
22	Correct	1063 ms	51148 KB	Output is correct
23	Correct	1161 ms	56280 KB	Output is correct
24	Correct	1261 ms	53324 KB	Output is correct
25	Correct	1176 ms	57624 KB	Output is correct
26	Correct	1245 ms	55384 KB	Output is correct
27	Correct	170 ms	14376 KB	Output is correct
28	Correct	156 ms	13944 KB	Output is correct
29	Correct	1566 ms	52824 KB	Output is correct
30	Correct	1239 ms	48868 KB	Output is correct
31	Correct	1305 ms	56296 KB	Output is correct
32	Correct	1239 ms	51184 KB	Output is correct
33	Correct	1276 ms	54932 KB	Output is correct
34	Correct	1634 ms	60044 KB	Output is correct
35	Correct	1342 ms	60376 KB	Output is correct
36	Correct	1483 ms	61284 KB	Output is correct
37	Correct	1460 ms	66140 KB	Output is correct
38	Correct	1432 ms	63636 KB	Output is correct
39	Correct	191 ms	15596 KB	Output is correct
40	Correct	201 ms	15512 KB	Output is correct
41	Correct	1936 ms	59292 KB	Output is correct
42	Correct	1793 ms	57088 KB	Output is correct
43	Correct	1677 ms	65528 KB	Output is correct
44	Correct	1752 ms	64572 KB	Output is correct
45	Correct	1716 ms	65800 KB	Output is correct
46	Correct	1578 ms	65048 KB	Output is correct
47	Correct	1731 ms	69032 KB	Output is correct
48	Correct	1663 ms	68212 KB	Output is correct
49	Correct	1697 ms	70068 KB	Output is correct
50	Correct	1717 ms	69660 KB	Output is correct
51	Correct	1315 ms	75036 KB	Output is correct
52	Correct	1352 ms	74692 KB	Output is correct
53	Correct	490 ms	51960 KB	Output is correct
54	Correct	1356 ms	57520 KB	Output is correct
55	Correct	1497 ms	59912 KB	Output is correct
56	Correct	1556 ms	63760 KB	Output is correct
57	Correct	929 ms	60252 KB	Output is correct