Submission #1340536

#TimeUsernameProblemLanguageResultExecution timeMemory
1340536axtelnVoting Cities (NOI22_votingcity)C++20
20 / 100
30 ms956 KiB
#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;
using ll = long long;
using pii = pair<ll,ll>;
using db = long double;

unordered_set<int> res;
vector<vector<pii>> graph(5001);
vector<int> ti;
int n,m,k;

struct State{
	ll cur,w;
	//vector<ll> path;
	
	bool operator<(const State& o) const{
		return tie(w,cur)>tie(o.w,o.cur);
	}
};

ll dijkstra(int st){
	vector<ll> dis(n+1,4e18);
	dis[st]=0;
	priority_queue<State> pq;
	pq.push({st,0});
	while (!pq.empty()){
		State t=pq.top();pq.pop();
		ll cur=t.cur,w=t.w;
		/*
		if (res.count(cur)){
			sort(t.path.begin(),t.path.end(),greater<ll>());
			
			for (int i:t.path){
				cout << i << " ";
			}cout << '\n';
			
			for (int i=0;i<5;i++){
				if (i==t.path.size()) break;
				for (int j=4;j>=0;j--){
					if (!((tickets>>j)&1)) continue;
					if (ti[j]!=-1 && ((t.path[i]/10)*(j+1)) > ti[j]){
						w-=((t.path[i]/10)*(j+1));
						w+=ti[j];
					}
				}
			}
			//cout << dis[cur] << " " << w << '\n';
			dis[cur]=min(dis[cur],w);
		}
		*/
		if (w > dis[cur]) continue;
		for (pii i:graph[cur]){
			ll nx=i.first,nw=i.second;
			if (dis[nx] < nw+w) continue;
			dis[nx]=nw+w;
			
			//t.path.push_back(nw);
			pq.push({nx,dis[nx]});
			//t.path.pop_back();
		}
	}
	ll mn=4e18;
	for (int i:res){
		mn=min(mn,dis[i]);
	}return mn;
}

int main(){
	fastio;
	cin >> n >> m >> k;
	for (int i=0;i<k;i++){
		int a;cin >> a;
		res.insert(a);
	}
	for (int i=0;i<m;i++){
		int st,en;ll c;
		cin >> st >> en >> c;
		graph[st].push_back({en,c});
		//graph[en].push_back({st,c});
	}
	int q;cin >> q;
	const int pow = 1<<5;
	for (int i=0;i<q;i++){
		int st,p1,p2,p3,p4,p5;
		cin >> st >> p1 >> p2 >> p3 >> p4 >> p5;
		
		//ti={p1,p2,p3,p4,p5};
		ll ans=dijkstra(st);
		/*
		for (int i=0;i<pow;i++){
			bool yes=1;
			for (int j=0;j<5;j++){
				if ((i>>j)&1 && ti[j]==-1)yes=0;
			}
			if (yes)ans=min(ans,dijkstra(st,mask));
		}
		*/
		if (ans!=4e18)cout << ans << "\n";
		else cout << -1 << "\n";
	}
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...