제출 #524544

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
524544		fatemetmhr	Wild Boar (JOI18_wild_boar)	C++17	62 / 100	8095 ms	160888 KiB

wild_boar

//  ~Be name khoda~  //

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define cl       clear
#define endll    '\n'

const int maxn  =  1e6   + 10;
const int maxn5 =  2e3   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  2e18;


ll h1[maxn5], h2[maxn5];
pair <ll, ll> dis[maxn5][2][maxn5];
int root[maxn5][2][maxn5];
int pa[maxn5];
set <pair<ll, pair<int, int>>> av;
vector <pair<int, int>> adj[maxn5];
int a[maxn5], b[maxn5];
ll c[maxn5];
int x[maxn];
pair <ll, ll> done[maxn];
int mxx[maxn];
int n;

inline void dij(int e, bool ty){
	for(int i = 0; i < n; i++){
		h1[i] = h2[i] = inf;
	}
	memset(pa, -1, sizeof pa);
	
	int uu = a[e], vu = b[e];
	if(ty){
		uu = b[e];
		vu = a[e];
	}
	
	bool ch = false;
		
	h1[vu] = 0;
	pa[vu] = e;

	av.clear();
	
	for(int i = 0; i < n; i++){
		av.insert({h1[i], {i, 0}});
		av.insert({h2[i], {i, 1}});
	}
	
	while(!av.empty()){
		int  v = av.begin() -> se.fi, ty = av.begin() -> se.se;
		av.erase(av.begin());
		if(ch){
			cout << v << ' ' << ty << ' ' << h1[v] << ' ' << h2[v] << ' ' << pa[v] << '\n';
		}
		if(ty == 0){
			if(h1[v] >= inf)
				continue;
			for(auto p : adj[v]) if(p.se != pa[v] && (v != uu || p.fi != vu)){
				int u = p.fi;
				ll val = h1[v] + c[p.se];
				if(val <= h1[u]){
					av.erase({h1[u], {u, 0}});
					av.erase({h2[u], {u, 1}});
					h2[u] = h1[u];
					h1[u] = val;
					pa[u] = p.se;
					av.insert({h1[u], {u, 0}});
					av.insert({h2[u], {u, 1}});
				}
				else if(val < h2[u]){
					av.erase({h2[u], {u, 1}});
					h2[u] = val;
					av.insert({h2[u], {u, 1}});
				}
			}
		}
		else{
			if(h2[v] >= inf)
				continue;
			int i = pa[v];
			int u = a[i] == v ? b[i] : a[i];
			if(v != uu || u != vu){
				ll val = h2[v] + c[i];
				if(val <= h1[u]){
					av.erase({h1[u], {u, 0}});
					av.erase({h2[u], {u, 1}});
					h2[u] = h1[u];
					h1[u] = val;
					pa[u] = i;
					av.insert({h1[u], {u, 0}});
					av.insert({h2[u], {u, 1}});
				}
				else if(val < h2[u]){
					av.erase({h2[u], {u, 1}});
					h2[u] = val;
					av.insert({h2[u], {u, 1}});
				}
			}
		}
	}
	
	for(int i = 0; i < n; i++){
		dis[e][ty][i] = {h1[i], h2[i]};
		root[e][ty][i] = pa[i];
	}
	
}

inline bool get_ty(int e, int u, int v){
	return a[e] == v;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	
	int m, t, l; cin >> n >> m >> t >> l;
	for(int i = 0; i < m; i++){
		cin >> a[i] >> b[i] >> c[i];
		a[i]--; b[i]--;
		adj[a[i]].pb({b[i], i});
		adj[b[i]].pb({a[i], i});
	}
	
	for(int i = 0; i < m; i++){
		dij(i, 0);
		dij(i, 1);
	}

	for(int i = 0; i < l; i++){
		cin >> x[i];
		x[i]--;
	}
	int a, b; cin >> a >> b;
	a--; b--;
	x[a] = b;
	
	/*
	for(int i = 0; i < m; i++) for(int j = 0; j < n; j++){
		cout << ::a[i] << ' ' << ::b[i] << " * " << j << ' ' << dis[i][0][j].fi << ' ' << dis[i][0][j].se << endl;
		cout << dis[i][1][j].fi << ' ' << dis[i][1][j].se << ' ' << root[i][1][j] << endl;
	}
	//*/
	

	for(int i = 0; i < l; i++){
		if(i == 0){
			done[0] = {0, 0};
			mxx[0] = adj[x[0]][0].se;
		}
		else{
			int u = x[i - 1], v = x[i];
			done[i].fi = inf;
			int opt = mxx[i - 1];
			for(auto p : adj[u]){
				int z = p.fi, id = p.se;
				ll val, val2;
				if(id != mxx[i - 1]){
					val = done[i - 1].fi + dis[id][get_ty(id, u, z)][v].fi + c[id];
					val2 = done[i - 1].fi + dis[id][get_ty(id, u, z)][v].se + c[id];
				}
				else{
					val = done[i - 1].se + dis[id][get_ty(id, u, z)][v].fi + c[id];
					val2 = done[i - 1].se + dis[id][get_ty(id, u, z)][v].se + c[id];
				}
				if(val <= done[i].fi){
					opt = id;
					done[i].fi = val;
					done[i].se = val2;
					mxx[i] = root[id][get_ty(id, u, z)][v];
				}
			
			}
			
			for(auto p : adj[u]){
				int z = p.fi, id = p.se;
				ll val = (root[id][get_ty(id, u, z)][v] == mxx[i] ? dis[id][get_ty(id, u, z)][v].se : dis[id][get_ty(id, u, z)][v].fi) + c[id];
				//cout << "alright " << z << ' ' << id << ' ' << val << ' ' << done[i].se << endl;
				if(id != mxx[i - 1]){
					val += done[i - 1].fi;
				}
				else{
					val += done[i - 1].se;
				}
				if(val <= done[i].se){
					done[i].se = val;
				}
			
			}
		}
		//cout << i << ' ' << x[i] << ' ' << done[i].fi << ' ' << done[i].se << ' ' << mxx[i] << endl;
	}
	
	cout << (done[l - 1].fi == inf ? -1 : done[l - 1].fi) << endl;
	
	
}

/*
4 4 4 3
1 2 1
2 3 1
1 3 1
1 4 1
2
1
2
2 4
*/

컴파일 시 표준 에러 (stderr) 메시지

wild_boar.cpp: In function 'int main()':
wild_boar.cpp:167:8: warning: variable 'opt' set but not used [-Wunused-but-set-variable]
  167 |    int opt = mxx[i - 1];
      |        ^~~

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