uva 10537 Toll! Revisited(优先队列优化dijstra及变形)
大致题意:有两种节点,一种是大写字母,一种是小写字母。首先输入m条边,当经过小写字母时需要付一单位的过路费,当经过大写字母时,要付当前财务的1/20做过路费。问在起点最少需要带多少物品使到达终点时还有k个物品。当有多条符合条件的路径时输出字典序最小的一个。
思路:已知终点的权值,那么可以从终点向前推。求终点到起点的最短路径,然后按字典序打印路径。
比较难处理的是:向前推时前驱节点的权值计算。列个方程算算就可以了,主要时不能整除的情况。
计算前驱结点dis值的时候,同时记录(i,j)的边权值,这是打印路径的依据。
#include <stdio.h> #include <algorithm> #include <set> #include <map> #include <vector> #include <math.h> #include <string.h> #include <stack> #include <queue> #define LL long long #define _LL __int64 using 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 <int> 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 <pair<LL,int>, vector<pair<LL,int> >, greater<pair<LL,int> > > 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; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。