简介:
过路费(加强版)
需要运送一定的货物,路上会经过村庄和城镇,
都会缴纳不同数量的货物
求在起点最小需要携带的货物
分析:
一眼dp
设计状态f[i]表示到达i,最多需要的货物
然而这道题我耍了一个”小心眼“
因为是在Dijkstra章节的例题,当然是要用Dijkstra解决啦
由于每走一步,就要有花费,而且花费还和货物的数量有关
我的第一反应就是把边权赋成相应的负值,
但是这样还是无法优美的解决
原则:正难则反
所以我们这次从终点倒退
已知我们需要运达的货物数量
我们逆序进行dijkstra即可
我们在逆向计算花费的时候,如果下一个结点是小写字母,直接加一即可
但是如果下一个结点是大写字母,我们就要费点事了
我们需要二分答案(丧心病狂)
tip
开ll
在记录路径的时候,如果发现有字典序更小的选择
就修改一下pre,同时把ta 扔进queue里
大写字母的字典序要比小写字母小
输出又花了我好大的功夫,心累,感觉不会再爱了
//这里写代码片
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define ll long long
using namespace std;
const ll INF=1e15;
const int N=100;
int n,S,E,p[N];
struct node{
int x,y;
};
struct heapnode{
ll d;
int u;
bool operator <(const heapnode &a) const
{
return d>a.d;
}
};
struct Dijkstra{
int n,m;
vector<node> e;
vector<int> G[N];
int pre[N];
ll dis[N];
bool p[N];
void init()
{
n=52;
e.clear();
for (int i=1;i<=n;i++) G[i].clear();
}
void add(int u,int w)
{
e.push_back((node){u,w});
m=e.size();
G[u].push_back(m-1);
}
ll js(ll x)
{
ll l=x;
ll r=x*2LL;
ll mid,ans;
while (l<r)
{
mid=(l+r)/2;
ll k=mid/20;
if (mid%20) k++;
if (mid-k>=x)
{
r=mid;
ans=r;
}
else
{
l=mid+1;
}
}
return ans;
}
void dij(int s,ll z)
{
for (int i=1;i<=n;i++) dis[i]=INF;
for (int i=1;i<=n;i++) pre[i]=i;
memset(p,1,sizeof(p));
dis[s]=z;
priority_queue<heapnode> Q;
Q.push((heapnode){z,s});
while (!Q.empty())
{
heapnode now=Q.top(); Q.pop();
int u=now.u;
if (!p[u]) continue;
p[u]=0;
for (int i=0;i<G[u].size();i++)
{
node way=e[G[u][i]];
ll sum=dis[u];
if (way.y>26) sum++; //小写字母
else
{
sum=js(sum);
}
if (dis[way.y]>sum)
{
dis[way.y]=sum;
pre[way.y]=u;
Q.push((heapnode){dis[way.y],way.y});
}
else if (dis[way.y]==sum&&pre[way.y]>u)
{
pre[way.y]=u;
Q.push((heapnode){dis[way.y],way.y});
}
}
}
}
};
Dijkstra A;
char get(int x)
{
if (x<=26)
{
x--;
return 'A'+x;
}
else
{
x-=27;
return 'a'+x;
}
}
void print(int now) //方案输出
{
if (p[now]==now)
{
if (now!=S) printf("-");
printf("%c
",get(now)); //输出结束
return;
}
if (now==S)
{
printf("%c",get(now));
print(p[now]);
}
else
{
printf("-%c",get(now));
print(p[now]);
}
return;
}
int main()
{
int cnt=0;
scanf("%d",&n);
while (n!=-1)
{
A.init();
for (int i=1;i<=n;i++)
{
char a,b;
int aa,bb;
cin>>a>>b;
if (a>='A'&&a<='Z') aa=a-'A'+1;
else aa=a-'a'+27;
if (b>='A'&&b<='Z') bb=b-'A'+1;
else bb=b-'a'+27;
A.add(aa,bb);
A.add(bb,aa);
}
char SS,T;
ll sum;
cin>>sum>>SS>>T;
if (SS>='A'&&SS<='Z') S=SS-'A'+1;
else S=SS-'a'+27;
if (T>='A'&&T<='Z') E=T-'A'+1;
else E=T-'a'+27;
A.dij(E,sum);
for (int i=0;i<N;i++) p[i]=A.pre[i];
printf("Case %d:
",++cnt);
printf("%lld
",A.dis[S]);
print(S);
scanf("%d",&n);
}
}