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

 #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 ;

 }

巴特西

uva10537 dijkstra + 逆推

最新文章

热门文章