Submission #556163

#TimeUsernameProblemLanguageResultExecution timeMemory
556163pragmatistEvacuation plan (IZhO18_plan)C++17
29 / 100
643 ms83156 KiB
    #include <bits/stdc++.h>                            
     
    #define pb push_back
    #define sz(v) (int)v.size()
    #define all(v) v.begin(),v.end()
    #define rall(v) v.rbegin(),v.rend()
    #define x first
    #define y second
    #define nl "\n"
     
    using namespace std;
     
    typedef long long ll;
    typedef pair<long long, long long> pll;
    typedef pair <ll, ll> pii;
     
    const int N = (int)1e5 + 7;
    const int M = (int)7e6 + 7;
    const ll MOD = (ll)1e9 + 7;                    
    const int inf = (int)1e9 + 7;
    const ll INF = (ll)3e18 + 7;
     
    pii dir[] = {{-1, -1}, {1, 1}, {-1, 1}, {1, -1}};
     
    int n, m, k, s, t, ans, Q, d[N], e[N];
    int p[N], sz[N];
    int timer, tin[N], tout[N], up[N][18], mn[N][18], di[N];
    vector<pii> g[N], gr[N];
    bool used[N];
     
    int get(int v) {
    	if(p[v] == v) return v;
    	return p[v] = get(p[v]);
    }
     
    void comb(int u, int v) {
    	u = get(u);
    	v = get(v);
    	if(sz[u] > sz[v]) swap(u, v);
    	p[u] = v;
    	sz[v] += sz[u];
    }
     
    void calc(int v, int pr, int cst) {
        tin[v] = ++timer;
    	up[v][0] = pr;	
    	mn[v][0] = cst;
    	for(int i = 1; i <= 17; ++i) {
    		up[v][i] = up[up[v][i-1]][i-1];
    		mn[v][i] = min(mn[v][i-1], mn[up[v][i-1]][i-1]);
    	}
    	for(auto [to, w]: gr[v]) {
    		if(to != pr) {
    			di[to] = di[v] + 1;
    			calc(to, v, w);	
    		}
    	}	
    	tout[v] = ++timer;
    }
     
    bool is_parent(int u, int v) {
    	return tin[u] <= tin[v] && tout[u] >= tout[v];
    }       
     
    int lca(int u, int v) {
    	if(is_parent(u, v)) return u;
    	if(is_parent(v, u)) return v;
    	for(int i = 17; i >= 1; --i) {
    		if(!is_parent(up[u][i], v)) u = up[u][i];
    	}
    	return up[u][0];
    }
     
    int get(int u, int v) {
    	int k = lca(u, v), x = di[u] - di[k], y = di[v] - di[k];
    	int res = inf;	
      	for(int i = 0; i < 18; ++i) {
    		if(x >> i & 1) res = min(res, mn[u][i]), u = up[u][i];
    		if(y >> i & 1) res = min(res, mn[v][i]), v = up[v][i];
    	} 
    	return res;
    }
     
    void solve() {          	             
    	cin >> n >> m;
    	vector<pii> edge;
    	for(int i = 1; i <= n; ++i) sz[i] = 1, p[i] = i;
    	for(int i = 1; i <= m; ++i) {
    		int u, v, w;
    		cin >> u >> v >> w;
    		edge.pb({u, v});
    		g[u].pb({v, w});
    		g[v].pb({u, w});
    	}
     
    	cin >> k;
    	for(int i = 1; i <= n; ++i) d[i] = inf;
    	set<pii> q;
    	for(int i = 1; i <= k; ++i) {
    		int x;
    		cin >> x;
    		d[x] = 0;
    		q.insert({0, x});		
    	}
    	while(!q.empty()) {
    		int v = (*q.begin()).y;
    		q.erase(q.begin());
    		for(auto [to, w] : g[v]) {
    			if(d[v] + w < d[to]) {
    				q.erase({d[to], to});
    				d[to] = d[v] + w;
    				q.insert({d[to], to});
    			}
    		}
    	}
     
    	vector<pair<int, pii> > po;
    	for(auto [u, v] : edge)
    		po.pb({min(d[u], d[v]), {u, v}});
    	sort(rall(po));
    	for(int i = 0; i < m; ++i) {
    		int u = po[i].y.x, v = po[i].y.y;
    		if(get(u) != get(v)) {
    			//cout << u << ' ' << v << ' ' << po[i].x << nl;
    			gr[u].pb({v, po[i].x});
    			gr[v].pb({u, po[i].x});
    			comb(u, v);
    		}
    	}
    	calc(1, 1, inf);
    	cin >> Q;
    	while(Q--) {
    		cin >> s >> t;
    		cout << get(s, t) << nl;	
    	}
    }           
     
    signed main() {                   
    	ios_base::sync_with_stdio(NULL);
        cin.tie(0);
        cout.tie(0);
       	int test = 1;
    	//cin >> test;
    	for(int i = 1; i <= test; ++i) {
            //cout << "Case " << i << ": ";
            solve();
        }
        return 0;
    }
    /*
    9 12
    1 9 4
    1 2 5
    2 3 7
    2 4 3
    4 3 6
    3 6 4
    8 7 10
    6 7 5
    5 8 1
    9 5 7
    5 4 12
    6 8 2
    2
    4 7
    5
    1 6
    5 3
    4 8
    5 8
    1 5
     
    */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...