제출 #173377

#제출 시각아이디문제언어결과실행 시간메모리
173377mat_vEvacuation plan (IZhO18_plan)C++14
100 / 100
1052 ms68760 KiB
#include <bits/stdc++.h>
#define mod 1000000007
#define pb push_back
#define mid(l, r) ((l)+(r))/2
#define len(a) (a).length()
#define sz(a) (a).size()
#define xx first
#define yy second
#define inf int(2e9)
#define ff(i, a, b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i, a, b) for(int (i) = (a); (i) >= (b); --(i))
#define maxn 200005

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

template<class T>
void print(const T niz[], const int siz)
{
    for(int i=0;i<siz;i++)
        cout << niz[i] << " ";
    cout << endl;
}

struct edge{
    int x;
    int y;
    int w;
};
bool cmp(edge a, edge b){
    return a.w > b.w;
}

int n, m, k;
vector<pii>graf[maxn];
int dist[maxn];
bool mark[maxn];
vector<int>koji;
bool bio[maxn];
vector<edge>e1;
vector<edge>e2;
vector<edge>chosen;


void djikstra(){
    priority_queue<pii, vector<pii>, greater<pii>>pq;
    for(auto c:koji)pq.push({0, c});
    while(!pq.empty()){
        pii tr = pq.top();
        pq.pop();
        dist[tr.yy] = min(tr.xx, dist[tr.yy]);
        for(auto c:graf[tr.yy]){
            if(dist[c.xx] > dist[tr.yy] + c.yy){
                dist[c.xx] = dist[tr.yy] + c.yy;
                pq.push({dist[tr.yy] + c.yy, c.xx});
            }
        }
    }

}

int dsu[maxn];
int findpar(int x){
    if(x == dsu[x])return x;
    return dsu[x] = findpar(dsu[x]);
}
void init(){
    ff(i,1,n)dsu[i] = i;
}
bool spojeni(int x, int y){
    return findpar(x) == findpar(y);
}

void unite(int x, int y){
    int a = findpar(x);
    int b = findpar(y);
    if(a == b)return;
    dsu[a] = b;
}

vector<pii> mst[maxn];
int deb[maxn];
int lca[maxn][20];
int par[maxn][20];
int in[maxn];
int out[maxn];
int br;
void root(int x, int pret, int dub, int val){
    deb[x] = dub;
    in[x] = br++;
    par[x][0] = pret;
    for(int i=1; i<18; i++){
        par[x][i] = par[par[x][i - 1]][i - 1];
    }
    lca[x][0] = val;
    for(int i=1; i<18; i++){
        lca[x][i] = min(lca[x][i - 1], lca[par[x][i - 1]][i - 1]);
    }
    for(auto c:mst[x]){
        if(c.xx == pret)continue;
        root(c.xx, x, dub + 1, c.yy);
    }
    out[x] = br;
}

bool insubtr(int x, int y){
    /// y u x
    if(x == 0)return 1;
    if(in[y] > in[x] && in[y] < out[x])return 1;
    return 0;
}

int ancestor(int x, int y){
    if(x == y)return x;
    if(insubtr(x, y))return x;
    if(insubtr(y, x))return y;
    for(int i=17; i>=0; i--){
        if(!insubtr(par[x][i], y))x = par[x][i];
    }
    return par[x][0];
}

int res(int x, int cale){
    int res = 1e9;
    for(int i=17; i>=0; i--){
        if(par[x][i] == cale){
            res = min(res, lca[x][i]);
            return res;
        }
        if(!insubtr(par[x][i], cale)){
            res = min(res, lca[x][i]);
            x = par[x][i];
        }
    }
    return res;
}
int upit(int x, int y){
    int cale = ancestor(x, y);
    return min(res(x, cale), res(y, cale));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n >> m;
    ff(i,0,m - 1){
        int x,y,z; cin >> x >> y >> z;
        graf[x].pb({y,z}); graf[y].pb({x,z});
        e1.pb({x,y,z});
    }
    ff(i,1,n)dist[i] = 1e9;
    cin >> k;
    ff(i,0,k - 1){
        int x;
        cin >> x;
        mark[x] = 1;
        koji.pb(x);
    }
    djikstra();
    init();
    for(auto c:e1){
        e2.pb({c.x, c.y, min(dist[c.x], dist[c.y])});
    }
    sort(e2.begin(), e2.end(), cmp);
    for(auto c:e2){
        int prvi = c.x;
        int drugi = c.y;
        if(spojeni(prvi,drugi))continue;
        unite(prvi, drugi);
        chosen.pb(c);
        mst[c.x].pb({c.y, c.w});
        mst[c.y].pb({c.x, c.w});
    }
    root(1,0,0,1e9);
    int q;
    cin >> q;
    while(q -- ){
        int a,b;
        cin >> a >> b;
        cout << upit(a, b) << endl;
        //dfs(a,0,dist[a]);
        //cout << res[b] << endl;
    }
    return 0;
}
#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...