uva10537 dijkstra + 逆推

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 计算出每个点到终点的最优的过路费，再来一次贪心取最小的结果。

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <string.h>
  4 #include <vector>
  5 #include <queue>
  6 #include <map>
  7 #include <cstdio>
  8 using namespace std;
  9 const int maxn=100;
 10 const long long INF = 1LL<<60;
 11 typedef long long LL;
 12 int hash_num(char c){
 13     if(c>='A'&&c<='Z') return c-'A';
 14     else return c-'a'+26;
 15 }
 16 char hash_char(int c){
 17    if(c>=0&&c<26) return c+'A';
 18    else return c-26+'a';
 19 }
 20 int st,ed;
 21 LL d[maxn];
 22 bool G[maxn][maxn],mark[maxn];
 23 LL projud(LL item, int next){
 24     if(next<26) return item-(item+19)/20;
 25     return item-1;
 26 }
 27 LL jud(int u){
 28    if(u >= 26) return d[u]+1;
 29       LL  v = d[u];
 30        LL ans=0;
 31        ans=v;
 32        while(true){
 33           LL d=v/20;
 34           v=v%20;
 35           ans+=d;
 36           v+=d;
 37           if(d==0)break;
 38        }
 39        if(v) ans++;
 40        return ans;
 41 }
 42 LL forward(LL item, int next) {
 43   if(next < 26) return item - (item + 19) / 20;
 44   return item - 1;
 45 }
 46 struct Head{
 47    LL d; int u;
 48    bool operator < (const Head &r)const {
 49      return d>r.d;
 50    }
 51    Head (LL dd =0, int uu = 0){
 52       d=dd; u = uu;
 53    }
 54 };
 55 void print(LL p){
 56      int nod=52;
 57       memset(mark,false,sizeof(mark));
 58       for(int i =0; i<nod ; i++ )d[i]=INF;
 59        d[ed]=p;
 60       priority_queue<Head> Q;
 61       Q.push(Head(p,ed));
 62       while(!Q.empty()){
 63            Head x= Q.top(); Q.pop();
 64            if(mark[x.u]) continue;
 65            mark[x.u]=true;
 66            for(int i=0; i<nod; ++i){
 67              LL pe =   jud(x.u);
 68              if(mark[i]==false&&G[i][x.u]&&pe<d[i]){
 69                d[i] = pe;
 70                Q.push(Head(d[i],i));
 71              }
 72            }
 73       }
 74 
 75     int u=st;
 76     printf("%lld
",d[st]);
 77     printf("%c",hash_char(u));
 78 
 79     LL item = d[st];
 80   while(u != ed ){
 81     int next;
 82     for(next = 0; next < nod; next++) if(G[u][next] && forward(item, next) >= d[next]) break;
 83     item = d[next];
 84     printf("-%c", hash_char(next));
 85     u = next;
 86   }
 87     printf("
");
 88 }
 89 int main()
 90 {
 91     int n,cas=0;
 92     char s1[9],s2[9];
 93 
 94     while(scanf("%d",&n)==1&&n!=-1){
 95       memset(G,false,sizeof(G));
 96 
 97         for(int i= 0; i<n; ++i){
 98              scanf("%s%s",s1,s2);
 99              int u = hash_num(s1[0]);
100              int v = hash_num(s2[0]);
101             if(u==v)continue;
102              G[u][v]=G[v][u]=true;
103 
104 
105         }
106         LL p;
107         scanf("%lld%s%s",&p,s1,s2);
108         st = hash_num(s1[0]); ed = hash_num(s2[0]);
109         printf("Case %d:
",++cas);
110         print(p);
111     }
112     return 0;
113 }