网站公司优势,网站优化免费软件,html网站分页怎么做,百度商家版下载题意#xff1a;N点M边的无向图#xff0c;边上有线性不下降的温度#xff0c;给固定入口S#xff0c;有E个出口。逃出去#xff0c;使最大承受温度最小。输出该温度#xff0c;若该温度超过H#xff0c;输出-1。 羞涩的题意 显然N*H的复杂度dp[n][h]表示到达n最大温度为…题意N点M边的无向图边上有线性不下降的温度给固定入口S有E个出口。逃出去使最大承受温度最小。输出该温度若该温度超过H输出-1。 羞涩的题意 显然N*H的复杂度dp[n][h]表示到达n最大温度为h的最小时间由于温度不下降这样不会更差故可以这么搞 一开始读错题了以为是温度累加什么鬼... 然后分别写了2种方法二分和不二分的 1 #include cstdio2 #include cstring3 #include iostream4 #include cmath5 #include algorithm6 #include vector7 #include string8 #include set9 #include queue10 using namespace std;11 12 #define ll long long13 #define MP make_pair14 15 #define inf 0x3f3f3f3f16 #define eps 1e-817 18 #define maxn 11019 struct edge{20 int v,nxt;21 int w,r,p;22 }e[maxn*maxn*2];23 int head[maxn], sz;24 void init(){sz0;memset(head,-1,sizeof(head));}25 void addedge(int u,int v,int w,int ri,int pi){26 e[sz].vv,e[sz].nxthead[u];27 e[sz].ww,e[sz].rri,e[sz].ppi;28 head[u]sz;29 }30 int dp[maxn][10010];31 bool ed[maxn];32 bool ins[maxn][10010];33 int pre[maxn][10010][2];34 int getout;35 void dfs(int u,int hp,int S,int cnt){36 if(uS){printf(%d %d,cnt1,u);return ;}37 dfs(pre[u][hp][0],pre[u][hp][1],S,cnt1);38 printf( %d,u);39 }40 bool check(int mahp, int S){41 memset(dp,0x3f,sizeof(dp));42 dp[S][0] 0;43 memset(ins,false,sizeof(ins));44 ins[S][0] true;45 queuepairint,int que;46 que.push(MP(S,0));47 if(ed[S]){getout S;return true;}48 while(!que.empty()){49 int u que.front().first;50 int hp que.front().second;51 int t dp[u][hp];52 que.pop();53 ins[u][hp] false;54 for(int ihead[u];i!-1;ie[i].nxt){55 int v e[i].v;56 int w e[i].w;57 int r e[i].r;58 int p e[i].p;59 ll tmp rp*(tw);60 if(tmpmahp) continue;61 int hp2 max(hp,int(tmp));62 if(dp[v][hp2]dp[u][hp]w){63 pre[v][hp2][0] u;64 pre[v][hp2][1] hp;65 if(ed[v]){getout v;return true;}66 dp[v][hp2] dp[u][hp]w;67 if(ins[v][hp2]false){68 ins[v][hp2] true;69 que.push(MP(v,hp2));70 }71 }72 }73 }74 return false;75 }76 int main(){77 int n,m,H,S,E;78 while(~scanf(%d%d%d%d%d,n,m,H,S,E)){79 memset(ed,false,sizeof(ed));80 init();81 for(int i0;im;i){82 int u,v,w,r,p;83 scanf(%d%d%d%d%d,u,v,w,r,p);84 addedge(u,v,w,r,p);85 addedge(v,u,w,r,p);86 }87 for(int i0;iE;i){88 int tmp;89 scanf(%d,tmp);90 ed[tmp] true;91 }92 int l0,rH1;93 while(lr){94 int mid (lr)/2;95 if(check(mid,S)) r mid;96 else l mid1;97 }98 if(rH){99 puts(YES);
100 printf(%d\n,r);
101 check(r,S);
102 dfs(getout,r,S,0);
103 puts();
104 }else puts(NO);
105 }
106 return 0;
107 } 二分代码 1 #include cstdio2 #include cstring3 #include iostream4 #include cmath5 #include algorithm6 #include vector7 #include string8 #include set9 #include queue10 using namespace std;11 12 #define ll long long13 #define MP make_pair14 15 #define inf 0x3f3f3f3f16 #define eps 1e-817 18 #define maxn 11019 struct edge{20 int v,nxt;21 int w,r,p;22 }e[maxn*maxn*2];23 int head[maxn], sz;24 void init(){sz0;memset(head,-1,sizeof(head));}25 void addedge(int u,int v,int w,int ri,int pi){26 e[sz].vv,e[sz].nxthead[u];27 e[sz].ww,e[sz].rri,e[sz].ppi;28 head[u]sz;29 }30 int dp[maxn][10010];31 bool ed[maxn];32 bool ins[maxn][10010];33 int pre[maxn][10010][2];34 void dfs(int u,int hp,int S,int cnt){35 if(uS){printf(%d %d,cnt1,u);return ;}36 dfs(pre[u][hp][0],pre[u][hp][1],S,cnt1);37 printf( %d,u);38 }39 pairint,int spfa(int mahp, int S){40 int getout-1,ans mahp1;41 memset(dp,0x3f,sizeof(dp));42 dp[S][0] 0;43 memset(ins,false,sizeof(ins));44 ins[S][0] true;45 queuepairint,int que;46 que.push(MP(S,0));47 if(ed[S]) return MP(S,0);48 while(!que.empty()){49 int u que.front().first;50 int hp que.front().second;51 int t dp[u][hp];52 que.pop();53 ins[u][hp] false;54 if(hpans) continue;55 for(int ihead[u];i!-1;ie[i].nxt){56 int v e[i].v;57 int w e[i].w;58 int r e[i].r;59 int p e[i].p;60 ll tmp rp*(tw);61 if(tmpmahp) continue;62 int hp2 max(hp,int(tmp));63 if(hp2ans) continue;64 if(dp[v][hp2]dp[u][hp]w){65 pre[v][hp2][0] u;66 pre[v][hp2][1] hp;67 if(ed[v]){68 getout v;69 ans hp2;70 }71 dp[v][hp2] dp[u][hp]w;72 if(ins[v][hp2]false){73 ins[v][hp2] true;74 que.push(MP(v,hp2));75 }76 }77 }78 }79 return MP(getout,ans);80 }81 int main(){82 int n,m,H,S,E;83 while(~scanf(%d%d%d%d%d,n,m,H,S,E)){84 memset(ed,false,sizeof(ed));85 init();86 for(int i0;im;i){87 int u,v,w,r,p;88 scanf(%d%d%d%d%d,u,v,w,r,p);89 addedge(u,v,w,r,p);90 addedge(v,u,w,r,p);91 }92 for(int i0;iE;i){93 int tmp;94 scanf(%d,tmp);95 ed[tmp] true;96 }97 pairint,int cur spfa(H,S);98 int getout cur.first;99 int ans cur.second;
100 if(getout!-1){
101 puts(YES);
102 printf(%d\n,ans);
103 dfs(getout,ans,S,0);
104 puts();
105 }else puts(NO);
106 }
107 return 0;
108 } 非二分代码 转载于:https://www.cnblogs.com/nextbin/p/4358468.html
