uva 10537 Toll! Revisited(优先队列优化dijstra及变形)-白红宇

uva 10537 Toll! Revisited(优先队列优化dijstra及变形)

阅读量：7070 次

发布时间：2019-06-28

本文共 2654 字，大约阅读时间需要 8 分钟。

大致题意：有两种节点，一种是大写字母，一种是小写字母。

首先输入m条边。当经过小写字母时须要付一单位的过路费。当经过大写字母时，要付当前財务的1/20做过路费。

问在起点最少须要带多少物品使到达终点时还有k个物品。

当有多条符合条件的路径时输出字典序最小的一个。

思路：已知终点的权值，那么能够从终点向前推。

求终点到起点的最短路径，然后按字典序打印路径。

比較难处理的是：向前推时前驱节点的权值计算。列个方程算算就能够了，主要时不能整除的情况。

计算前驱结点dis值的时候，同一时候记录(i,j)的边权值。这是打印路径的根据。

#include 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #define LL long long#define _LL __int64using namespace std;const int INF = 0x3f3f3f3f;const int maxm = 1010;const int maxn = 60;struct node{ int v,w; int next;}edge[maxm];int m;int pre[maxn],cnt;int start,end;LL dis[maxn],p;int vis[maxn];vector 
              
                ans;void init(){ cnt = 0; memset(pre,-1,sizeof(pre)); for(int i = 0; i < maxm; i++) edge[i].w = 0;}void add(int u, int v){ edge[cnt].v = v; edge[cnt].next = pre[u]; pre[u] = cnt++;}void dijstra(){ priority_queue 
               
                
                 , vector
                 
                  
                    >, greater
                   
                    
                      > > que; while(!que.empty()) que.pop(); memset(dis,INF,sizeof(dis)); memset(vis,0,sizeof(vis)); dis[end] = p; que.push(make_pair(dis[end],end)); while(!que.empty()) { int u = que.top().second; que.pop(); if(vis[u]) continue; vis[u] = 1; for(int i = pre[u]; i != -1; i = edge[i].next) //松弛相邻节点 { if(vis[edge[i].v]) continue; int v = edge[i].v; if(u < 26) { //计算前驱结点的权值，推断是否整除，若不整除，尝试加1继续推断 if(dis[u]%19 == 0) { if(dis[v] > dis[u]/19*20) { dis[v] = dis[u]/19*20; edge[i].w = edge[i^1].w = dis[v]-dis[u]; que.push(make_pair(dis[v],v)); } } else if( (dis[u]+1)%19 ) { if(dis[v] > (dis[u]+1)*20/19) { dis[v] = (dis[u]+1)*20/19; edge[i].w = edge[i^1].w = dis[v]-dis[u]; que.push(make_pair(dis[v],v)); } } else { if(dis[v] > (dis[u]+1)*20/19-1 ) { dis[v] = (dis[u]+1)*20/19-1; edge[i].w = edge[i^1].w = dis[v]-dis[u]; que.push(make_pair(dis[v],v)); } } } else { if(dis[v] > dis[u]+1) { dis[v] = dis[u]+1; edge[i].w = edge[i^1].w = 1; que.push(make_pair(dis[v],v)); } } } }}void solve(){ ans.clear(); int now; now = start; ans.push_back(now); while(now != end) { int tmp = 1<<6; for(int i = pre[now]; i != -1; i = edge[i].next) { int v = edge[i].v; //由于输出字典序最小的，所以求出满足dis[now] - dis[v] == edge[i].w中最小的v if(dis[now] - dis[v] == edge[i].w && v < tmp) { tmp = v; } } ans.push_back(tmp); now = tmp; } printf("%c",ans[0]+'A'); for(int i = 1; i < (int)ans.size(); i++) printf("-%c",ans[i]+'A'); printf("\n");}int main(){ int item = 1; char t1,t2; while(~scanf("%d",&m)) { if(m == -1) break; init(); getchar(); for(int i = 0; i < m; i++) { scanf("%c %c",&t1,&t2); getchar(); add(t1-'A',t2-'A'); add(t2-'A',t1-'A'); } scanf("%lld %c %c",&p,&t1,&t2); start = t1-'A'; end = t2-'A'; dijstra(); printf("Case %d:\n",item++); printf("%lld\n",dis[start]); solve(); } return 0;}