Submission #288277

#	Time	Username	Problem	Language	Result	Execution time	Memory
288277		Blagojce	Wild Boar (JOI18_wild_boar)	C++11	47 / 100	16366 ms	1048576 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;

int n, m, t, len;

ll dist[2][501][100000];
bool vis[2][501][100000];

void solve(){
	cin >> n >> m >> t >> len;
	vector<pii> g[n];
	int l[m+1], r[m+1];
	fr(i, 0, m){
		int u, v, w;
		cin >> u >> v >> w;
		--u, --v;
		l[i+1] = u, r[i+1] = v;
		g[u].pb({i+1, w});
		g[v].pb({i+1, w});
	}
	int a[len];
	fr(i, 0, len){
		cin >> a[i];
		--a[i];
	}
	
	fr(I, 0, t){
		int p, q;
		cin >> p >> q;
		a[p-1] = q-1;
		
		l[0] = r[0] = a[0];
		
		memset(vis, false, sizeof(vis));
		
		fr(i, 0, 2) fr(j, 0, m+1) fr(k, 0, len) dist[i][j][k] = inf;
		
		
		pq<pair<ll, pair<int,pii> > > Q;
		Q.push({0, {0, {0, 0}}});
		dist[0][0][0] = 0;
		
		while(!Q.empty()){
			int side = Q.top().nd.st;
			int edge = Q.top().nd.nd.st;
			int k = Q.top().nd.nd.nd;
			
			Q.pop();
			if(vis[side][edge][k]) continue;
			vis[side][edge][k] = true;
			
			int u;
			if(side == 0){
				u = l[edge];
			}
			else{
				u = r[edge];
			}
			
			for(auto e : g[u]){
				if(e.st == edge) continue;
				
				int newside, newnode;
				if(u == l[e.st]){
					newnode = r[e.st];
					newside = 1;
				}
				else{
					newnode = l[e.st];
					newside = 0;
				}
				
				int newk = k;
				if(newnode == a[k+1]){
					newk += 1;
				}
				
				if(dist[side][edge][k] + e.nd < dist[newside][e.st][newk]){
					dist[newside][e.st][newk] = dist[side][edge][k] + e.nd;
					Q.push({-dist[newside][e.st][newk], {newside,{e.st, newk}}});
				}
				
				
			}
		}
		ll ans = inf;
		
		for(auto u : g[a[len-1]]){
			int side;
			if(a[len-1] == l[u.st]) side = 0;
			else side = 1;
			ans = min(ans, dist[side][u.st][len-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: 35 / 35
• Subtask 3: 0 / 15
• Subtask 4: 0 / 38