JZOJ3800 敗屩妖

2022-09-23 07:46:59 字數 679 閱讀 4713

裸題。二分\(c\),然後只走邊權大於\(mid\)的邊,把每一個連通塊染色。然後再列舉每一個詢問,如果均不能到達則\(mid\)是一個合法方案,反之不行。

時間複雜度\(o((n+m)\log maxdis)\)

#include #include #include #include using namespace std;

const int n=100010,m=600010;

int n,m,q,maxn,tot,head[n],pos[n];

struct edge

e[m];

struct ask

ask[n];

void add(int from,int to,int dis)

void dfs(int x,int id,int mid)

bool check(int mid)

int main()

for (int i=1;i<=q;i++)

int l=0,r=maxn,mid;

while (l<=r)

printf("%d",r+1);

return 0;

}