济南做外贸网站,东莞网站建设seo推广,seo快速排名是什么,盐田区网站建设正题
题目链接:https://gmoj.net/senior/#main/show/5248 题目大意 nnn个点的一棵树#xff0c;有mmm张票(v,k,w)(v,k,w)(v,k,w)表示可以在点vvv买#xff0c;可以走kkk步以内#xff0c;价格为www。
一个时间只能有一个票#xff0c;每次询问一个点到根节点需要的最少票…正题
题目链接:https://gmoj.net/senior/#main/show/5248 题目大意
nnn个点的一棵树有mmm张票(v,k,w)(v,k,w)(v,k,w)表示可以在点vvv买可以走kkk步以内价格为www。
一个时间只能有一个票每次询问一个点到根节点需要的最少票钱。 解题思路
设fif_{i}fi表示iii到根节点的价钱然后vectorvectorvector存票倍增转移即可。
时间复杂度O(nlogn)O(n\log n)O(nlogn) codecodecode
#includecstdio
#includecstring
#includealgorithm
#includevector
#define mp(x,y) make_pair(x,y)
using namespace std;
const int N1e510,T20;
struct node{int to,next;
}a[N*2];
int n,m,tot,ls[N],f[N][T],g[N][T];
vectorpairint,int q[N];
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(int x,int fa){for(int i0;iq[x].size();i){int nowfa,kq[x][i].first,wq[x][i].second;for(int iT-1;i0;i--)if((ki)1)g[x][0]min(g[x][0],g[now][i]w),nowf[now][i];}for(int i1;iT;i)g[x][i]min(g[x][i-1],g[f[x][i-1]][i-1]),f[x][i]f[f[x][i-1]][i-1];for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa)continue;f[y][0]x;dfs(y,x);}return;
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i){int x,y;scanf(%d%d,x,y);addl(x,y);addl(y,x);}for(int i1;im;i){int x,y,w;scanf(%d%d%d,x,y,w);q[x].push_back(mp(y,w));}memset(g,0x3f,sizeof(g));g[1][0]0;dfs(1,1);scanf(%d,m);while(m--){int x;scanf(%d,x);printf(%d\n,g[x][0]);}
}
