oj.uz

Submission #287718

# Submission time Handle Problem Language Result Execution time Memory
287718 2020-08-31T22:47:24 Z Blagojce Wild Boar (JOI18_wild_boar) C++11
0 / 100
 1 ms 384 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -