http://acm.hdu.edu.cn/showproblem.php?pid=6071

题意:

1、2、3、4四个点依次形成一个环,现在有个人从2结点出发,每次可以往它相邻的两个结点跑,求最后回到2结点并且不少于K的最短距离。

思路:

官方题解:

HDU 6071 Lazy Running(很牛逼的最短路)-LMLPHP

最后的答案可以表示为:$ans=p*(2w)+m$,这样一来,m的取值范围就是$(0<=m<2w)$,而因为m的不同,p值也会有所不同。所以我们用 d [ i ] [ m ]表示从起点出发,最后到达 i 点,距离对2w取模为m时的最小距离,这个计算一下最短路即可。

最后只需要枚举m,如果此时d [ 2 ] [ m ]不足K的话,那么就再加上2w补足即可,在所有的m中取最小值。

 #include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<sstream>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<int,ll> pll;
const ll INF = ;
const int maxn=1e6+; ll k;
ll m;
ll d[];
ll dis[][maxn];
vector<pll> G[]; struct HeapNode
{
int u; ll w;
HeapNode(int x, ll y) :u(x), w(y){}
bool operator <(const HeapNode& rhs) const{
return w>rhs.w;
}
}; void dijkstra()
{
priority_queue<HeapNode> Q;
for(int i=;i<;i++)
for(int j=;j<=m;j++) dis[i][j]=INF; Q.push(HeapNode(,));
while(!Q.empty())
{
HeapNode p=Q.top(); Q.pop();
int u=p.u;
ll w=p.w; for(int i=;i<G[u].size();i++)
{
int v=G[u][i].first;
ll new_w=G[u][i].second+w;
if(dis[v][new_w%m]>new_w)
{
dis[v][new_w%m]=new_w;
Q.push(HeapNode(v,new_w));
}
}
}
} int main()
{
//freopen("in.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
scanf("%lld",&k);
for(int i=;i<;i++) G[i].clear();
for(int i=;i<;i++)
{
scanf("%lld",&d[i]);
G[i].push_back(make_pair((i+)%,d[i]));
G[(i+)%].push_back(make_pair(i,d[i]));
}
m=*min(d[],d[]);
dijkstra(); ll ans=INF;
for(int i=;i<m;i++)
{
ll tmp=k-dis[][i];
if (tmp<=) ans=min(ans,dis[][i]);
else ans=min(ans,dis[][i]+(ll)ceil((long double)tmp/m)*m);
}
printf("%lld\n",ans);
}
return ;
}
05-11 19:43