Submission #287718

#	Time	Username	Problem	Language	Result	Execution time	Memory
287718		Blagojce	Wild Boar (JOI18_wild_boar)	C++11	0 / 100	1 ms	384 KiB

wild_boar

#include <bits/stdc++.h> 
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,ll> pii;
 
const int i_inf = 1e9;
const ll inf = 1e18;
const ll mod = 1000000007;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;
 
mt19937 _rand(time(NULL));
clock_t timer = clock();
const int mxn = 2e5+5;
 
const ll A = 911382323;
const ll B = 972663749;

void solve(){
	int n, m, t, l;
	cin >> n >> m >> t >> l;
	vector<pii> g[n];
	fr(i, 0, m){
		int u, v, w;
		cin >> u >> v >> w;
		--u, --v;
		g[u].pb({v, w});
		g[v].pb({u, w});
	}
	int a[l];
	fr(i, 0, l){
		cin >> a[i];
		--a[i];
	}
	int p, q;
	cin >> p >> q;
	a[p-1] = q-1;
	bool vis[n][n][n];
	memset(vis, false, sizeof(vis));
	ll dist[n][n][n];
	fr(i, 0, n) fr(j, 0, n) fr(k, 0, n) dist[i][j][k] = inf;
	pq<pair<ll, pair<int,pii> > > Q;
	Q.push({0, {a[0], {a[0], 0}}});
	dist[a[0]][a[0]][0] = 0;
	while(!Q.empty()){
		int u = Q.top().nd.st;
		int pr = Q.top().nd.nd.st;
		int k = Q.top().nd.nd.nd;
		if(k == l-1){
			cout<<dist[u][pr][k]<<endl;
			return;
		}
		
		Q.pop();
		if(vis[u][pr][k]) continue;
		vis[u][pr][k] = true;
		for(auto e : g[u]){
			if(e.st == pr) continue;
			
			int newk = k;
			if(dist[u][pr][k] + e.nd < dist[e.st][u][newk]){
				dist[e.st][u][newk] = dist[u][pr][k] + e.nd;
				Q.push({-dist[e.st][u][newk], {e.st,{u, newk}}});
			}
			
			if(e.st == a[k+1]){
				newk += 1;
				
				if(dist[u][pr][k] + e.nd < dist[e.st][u][newk]){
					dist[e.st][u][newk] = dist[u][pr][k] + e.nd;
					Q.push({-dist[e.st][u][newk], {e.st,{u, newk}}});
				}
			}
		}
	}
	cout<<-1<<endl;
	
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int tc = 1;
	//cin >> tc;
	while(tc--) solve();
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 35
• Subtask 3: 0 / 15
• Subtask 4: 0 / 38