제출 #173376

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
173376		mat_v	Evacuation plan (IZhO18_plan)	C++14	41 / 100	4046 ms	48492 KiB

plan

#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 res[maxn];
void dfs(int x, int pret, int sol){
    res[x] = min(sol, dist[x]);
    for(auto c:mst[x]){
        if(c.xx == pret)continue;
        dfs(c.xx, x, res[x]);
    }
}



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});
    }
    int q;
    cin >> q;
    while(q -- ){
        int a,b;
        cin >> a >> b;
        dfs(a,0,dist[a]);
        cout << res[b] << endl;
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 0 / 46