21:49:45 2015-03-09
传送 http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1478
这题说的是运送货物需要交纳过路费。进入一个村庄需要交纳1个单位的货物，而进入一个城镇是每20个单位的货物中就要上缴1个单位的（70要上交4个）问选择哪条道路使得过路费最少，
这题我们知道了终太 ， 那么我们就可以逆推回去， 比如说我们知道了最后一站我们就可以逆推回上一站， 采用dijkstra 计算出每个点到终点的最优的过路费，再来一次贪心取最小的结果。
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <map>
#include <cstdio>
using namespace std;
const int maxn=;
const long long INF = 1LL<<;
typedef long long LL;
int hash_num(char c){
if(c>='A'&&c<='Z') return c-'A';
else return c-'a'+;
}
char hash_char(int c){
if(c>=&&c<) return c+'A';
else return c-+'a';
}
int st,ed;
LL d[maxn];
bool G[maxn][maxn],mark[maxn];
LL projud(LL item, int next){
if(next<) return item-(item+)/;
return item-;
}
LL jud(int u){
if(u >= ) return d[u]+;
LL v = d[u];
LL ans=;
ans=v;
while(true){
LL d=v/;
v=v%;
ans+=d;
v+=d;
if(d==)break;
}
if(v) ans++;
return ans;
}
LL forward(LL item, int next) {
if(next < ) return item - (item + ) / ;
return item - ;
}
struct Head{
LL d; int u;
bool operator < (const Head &r)const {
return d>r.d;
}
Head (LL dd =, int uu = ){
d=dd; u = uu;
}
};
void print(LL p){
int nod=;
memset(mark,false,sizeof(mark));
for(int i =; i<nod ; i++ )d[i]=INF;
d[ed]=p;
priority_queue<Head> Q;
Q.push(Head(p,ed));
while(!Q.empty()){
Head x= Q.top(); Q.pop();
if(mark[x.u]) continue;
mark[x.u]=true;
for(int i=; i<nod; ++i){
LL pe = jud(x.u);
if(mark[i]==false&&G[i][x.u]&&pe<d[i]){
d[i] = pe;
Q.push(Head(d[i],i));
}
}
} int u=st;
printf("%lld\n",d[st]);
printf("%c",hash_char(u)); LL item = d[st];
while(u != ed ){
int next;
for(next = ; next < nod; next++) if(G[u][next] && forward(item, next) >= d[next]) break;
item = d[next];
printf("-%c", hash_char(next));
u = next;
}
printf("\n");
}
int main()
{
int n,cas=;
char s1[],s2[]; while(scanf("%d",&n)==&&n!=-){
memset(G,false,sizeof(G)); for(int i= ; i<n; ++i){
scanf("%s%s",s1,s2);
int u = hash_num(s1[]);
int v = hash_num(s2[]);
if(u==v)continue;
G[u][v]=G[v][u]=true; }
LL p;
scanf("%lld%s%s",&p,s1,s2);
st = hash_num(s1[]); ed = hash_num(s2[]);
printf("Case %d:\n",++cas);
print(p);
}
return ;
}