怎样成立一个网站,管理咨询公司的运作模式,上海地区网站开发公司,网站建设属于正题
题目大意:https://www.luogu.org/problem/P4880 题目大意
一个无向图#xff0c;从bbb点出发#xff0c;目标在eee点#xff0c;TTT次移动在第aia_iai时移动到点xix_ixi。求最早多少能到。 解题思路
若一个点我们到不了我们就不用管它了#xff0c;所以我们只要…正题
题目大意:https://www.luogu.org/problem/P4880 题目大意
一个无向图从bbb点出发目标在eee点TTT次移动在第aia_iai时移动到点xix_ixi。求最早多少能到。 解题思路
若一个点我们到不了我们就不用管它了所以我们只要先算出单源最短路。然后枚举一波就好了。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includequeue
using namespace std;
const int N1e510;
struct edge_node{int to,next,w;
}a[10*N];
struct node{int t,w;
}p[N];
int n,m,b,e,tot,ans,t;
int ls[N],f[N];
bool v[N];
queueint q;
void addl(int x,int y,int w)
{a[tot].toy;a[tot].nextls[x];a[tot].ww;ls[x]tot;
}
void SPFA()
{memset(f,0x3f,sizeof(f));q.push(b);f[b]0;v[b]1;while(!q.empty()){int xq.front();q.pop();for(int ils[x];i;ia[i].next){int ya[i].to;if(f[x]a[i].wf[y]){f[y]f[x]a[i].w;if(!v[y]){v[y]1;q.push(y);}}}v[x]0;}
}
bool cmp(node x,node y)
{return x.ty.t;}
int main()
{scanf(%d%d%d%d,n,m,b,e);for(int i1;im;i){int x,y,w;scanf(%d%d%d,x,y,w);addl(x,y,w);addl(y,x,w);}scanf(%d,t);for(int i1;it;i)scanf(%d%d,p[i].t,p[i].w);SPFA();sort(p1,p1t,cmp);ans2147483647;for(int i1;it;i){if(f[e]p[i].t) ansmin(ans,max(f[e],p[i-1].t));ep[i].w;}ansmin(ans,max(f[e],p[t].t));printf(%d,ans);
}
