題目大意：給出一個 n * m 的矩陣，矩陣中有些許數字，兩個數字之間的距離如果小于 r 的話就是可達，到達一個數字后會消耗數字對應的體力值，問從最下面的數字到最上面的數字的最短路是多少，必須要保證體力值不能為負

題目分析：很容易寫出一個分層圖最短路，嚴格來說就是個二維最短路，d[ x ][ s ] 代表從起點到達點 x 時，消耗了 s 點體力的最短路，不過會 TLE，考慮剪枝

因為在這個題目中最短路的優先級最高，換句話說，在相同的一個點，肯定距離越近且體力消耗越少越好，如果當前 y 位置下，最短距離為 dis，且體力為 s，如果從 y 位置轉移過來得到的距離 dis' 和 s' ，有關系 dis' > dis && s' > s，顯然這個狀態一定不會為最后的最后狀態做出貢獻，直接減掉即可

代碼寫的有點丑，但還是貼上來吧

代碼：

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;const double eps=1e-8;int sgn(double x) {if(fabs(x)<=eps)return 0;if(x<0)return -1;elsereturn 1; }struct Node {int x,y,val;Node(int x,int y,int val):x(x),y(y),val(val){}bool operator<(const Node& t)const{return x<t.x;} };struct Edge {int to,next;double w; }edge[30*30*30*30];char maze[30][30];vector<Node>node;int head[30*30],cnt,sum;double d[30*30][25*25*10+100];pair<double,int>mmin[30*30];bool vis[30*30][25*25*10+100];void addedge(int u,int v,double w) {edge[cnt].to=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt++; }struct Node2 {double dis;int to,s;Node2(int to,double dis,int s):to(to),dis(dis),s(s){}bool operator<(const Node2& t)const{if(sgn(dis-t.dis)!=0)return sgn(dis-t.dis)>0;elsereturn s>t.s;} };void Dijkstra(int st) {for(int i=0;i<=node.size();i++){mmin[i]=make_pair(1e10,-1);for(int j=0;j<=sum;j++){d[i][j]=1e10;vis[i][j]=false;}}priority_queue<Node2>q;int s=node[st].val;q.push(Node2(st,0,s));d[st][s]=0;while(q.size()){Node2 cur=q.top();q.pop();int u=cur.to,s=cur.s;if(vis[u][s])continue;vis[u][s]=true;if(sgn(mmin[u].first-d[u][s])>0)//剪枝 mmin[u]=make_pair(d[u][s],s);for(int i=head[u];i!=-1;i=edge[i].next){int to=edge[i].to;double w=edge[i].w;int ss=node[to].val;if(s+ss>sum)continue;if(sgn(d[u][s]+w-mmin[to].first)>=0&&s+ss>=mmin[to].second)continue;if(d[to][s+ss]>d[u][s]+w){d[to][s+ss]=d[u][s]+w;q.push(Node2(to,w+cur.dis,s+ss));}}} }void init() {memset(head,-1,sizeof(head));cnt=0; }int main() { #ifndef ONLINE_JUDGEfreopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);init();int n,m,r,s;scanf("%d%d%d%d",&n,&m,&r,&s);for(int i=1;i<=n;i++)scanf("%s",maze[i]+1);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(maze[i][j]=='.')continue;node.push_back(Node(i,j,maze[i][j]-'0'));sum+=maze[i][j]-'0';}sum=min(sum,s);int st=0,ed=node.size()-1;for(int i=0;i<node.size();i++)for(int j=i+1;j<node.size();j++){double dis=hypot(node[i].x-node[j].x,node[i].y-node[j].y);if(sgn(dis-r)>0)continue;addedge(i,j,dis);addedge(j,i,dis);}Dijkstra(st);double ans=1e10;for(int i=0;i<=sum;i++)ans=min(ans,d[ed][i]);if(sgn(ans-1e10)==0)puts("impossible");elseprintf("%.15f\n",ans);return 0; }

?

總結

以上是生活随笔為你收集整理的中石油训练赛 - Bouldering(最短路+剪枝)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。