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

2020-12-13 01:47

阅读：284

标签：最短路

Toll! Revisited

大致题意：有两种节点，一种是大写字母，一种是小写字母。首先输入m条边，当经过小写字母时需要付一单位的过路费，当经过大写字母时，要付当前财务的1/20做过路费。问在起点最少需要带多少物品使到达终点时还有k个物品。当有多条符合条件的路径时输出字典序最小的一个。

思路：已知终点的权值，那么可以从终点向前推。求终点到起点的最短路径，然后按字典序打印路径。

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

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

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

void init()
{
    cnt = 0;
    memset(pre,-1,sizeof(pre));
    for(int i = 0; i , 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  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

uva 10537 Toll! Revisited(优先队列优化dijstra及变形),搜素材,soscw.com
uva 10537 Toll! Revisited(优先队列优化dijstra及变形)
标签：最短路
原文地址：http://blog.csdn.net/u013081425/article/details/25009311

上一篇：Spring Boot 打包分离依赖 JAR 和配置文件

下一篇：Java集合系列-HashMap 1.8(一)

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：uva 10537 Toll! Revisited(优先队列优化dijstra及变形)
文章链接：http://soscw.com/essay/24219.html

亲，登录后才可以留言！

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

评论

热门文章

推荐文章

最新文章

置顶文章