Submission #287752

#	Time	Username	Problem	Language	Result	Execution time	Memory
287752		Blagojce	Wild Boar (JOI18_wild_boar)	C++11	12 / 100	604 ms	1048580 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];
	}fr(I, 0, t){
	int p, q;
	cin >> p >> q;
	a[p-1] = q-1;
	bool ok[n];
	memset(ok, false, sizeof(ok));
	fr(i, 0, l) ok[a[i]] = true;
	bool vis[n][n][l];
	memset(vis, false, sizeof(vis));
	ll dist[n][n][l];
	fr(i, 0, n) fr(j, 0, n) fr(k, 0, l) 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;
		
		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(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}}});
			}
			
			
		}
	}
	ll ans = inf;
	fr(i, 0, n){
		ans = min(ans, dist[a[l-1]][i][l-1]);
	}
	
	
	if(ans == inf)cout<<-1<<endl;
	else cout<<ans<<endl;
	}
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int tc = 1;
	//cin >> tc;
	while(tc--) solve();
}
/*
5 10 1 10
1 2 8
1 3 5
1 4 2
1 5 1
2 3 7
2 4 9
2 5 6
3 4 10
3 5 10
4 5 6
4
2
4
3
5
3
1
4
3
5
3 5
*/

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