hdu6071神奇的最短路

传送门
题意是，有四个地点，1<->2<->3<->4<->1,是双向循环的，知道每一段的之间的长度，d12,d23,d34,d41,问题是要从2号点开始炮，最后回到2号点，问跑的总路程大于等于K米的最小值是多少。
首先我们让 w=min(d12,d23) ，那么如果存在一个合法的路程 k 必然会存在路程 k+2∗w 。让 d[x][v%(2∗w)] 表示从 2 出发到 x 点时 v=d[x][v%(2∗w)] 的最小值。跑一遍最短路计算出 d 数组。枚举区间 [0,2∗w−1] ，答案一定可以在这里面取到（如果不足 K ，不断加上 2∗w 直到大于 K）。如果 ans 为答案，ans%(2∗w)的余数一定在 [0,2∗w−1] 间，对于每种余数，我们都求到了得到这个余数的最小值。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef long long LL;
typedef pair<LL,int>P;
const int MAXN=30000*2+10;
const LL INF=1e18+100;
LL K,ans;
vector<P>G[5];
LL d[5][MAXN];///d[i][j] 表示到i点后距离为j%W的最短距离
void bfs(LL W)
{
d[2][0]=0;
priority_queue<P, vector<P>, greater<P> >que;///P<距离,节点>
que.push(P(0,2));
while(!que.empty())
{
P now=que.top();
que.pop();
LL dis;
int u=now.second;
for(int i=0;i<G[u].size();i++)
{
int
v=G[u][i].second;
dis=(d[u][now.first%W]+G[u][i].first);
if(dis<d[v][dis%W])
{
d[v][dis%W]=dis;
que.push(P(dis,v));
}
}
}
}
int main()
{
int T;
LL d1,d2,d3,d4;
cin>>T;
while(T--)
{
cin>>K>>d1>>d2>>d3>>d4;
G[1].push_back(P(d1,2));
G[2].push_back(P(d1,1));
G[2].push_back(P(d2,3));
G[3].push_back(P(d2,2));
G[3].push_back(P(d3,4));
G[4].push_back(P(d3,3));
G[4].push_back(P(d4,1));
G[1].push_back(P(d4,4));
LL W=min(d1,d2)*2;
for(int i=1;i<=4;i++)
{
for(int j=0;j<W;j++)
d[i][j]=INF;
}
ans=K/W*W+ (K%W>0) * W;///假设最短的是全是用W跑出来的
bfs(W);
LL nd,temp;
for(int i=0;i<W;i++)
{
if(d[2][i]>=K)
ans=min(ans,d[2][i]);
else
{
nd=K-d[2][i];
temp=nd/W*W+(nd%W>0)*W;
ans=min(ans,temp+d[2][i]);
}
}
cout<<ans<<endl;
for(int i=1;i<5;i++)
G[i].clear();
}
return 0;
}

最后

以上就是儒雅裙子为你收集整理的hdu6071神奇的最短路的全部内容，希望文章能够帮你解决hdu6071神奇的最短路所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。