Rinne Loves Graph

news/2024/5/22 16:43:44

Rinne Loves Graph (nowcoder.com)

链接:登录—专业IT笔试面试备考平台_牛客网
来源:牛客网
 

题目描述

Island 发生了一场暴乱!现在 Rinne 要和 Setsuna 立马到地上世界去。

众所周知:Island 是有一些奇怪的城镇和道路构成的(题目需要,游戏党勿喷),有些城镇之间用双向道路连接起来了,且每条道路有它自己的距离。但是有一些城镇已经被派兵戒严,虽然主角可以逆天改命强闯,但是为了体验该游戏的平衡性,他们只能穿过不超过 K 次被戒严的城镇。

定义“穿过”:从一个戒严的点出发到达任意一个点,都会使得次数加1

现在他们想从 1 号城镇最快的走到 n 号城镇(即出口),现在他们想让你告诉他们最短需要走多少路。

输入描述:

第一行三个整数 n,m,k,分别表示城镇数量,边数量和最多能闯过被戒严的城市的次数。
接下来 n 行,每行一个整数 1 或 0,如果为 1 则表示该城市已被戒严,0 则表示相反。
接下来 m 行,每行三个数 u,v,w,表示在 u 城镇和 v 城镇之间有一条长度为 w 的双向道路。

输出描述:

输出一行一个数字,表示从 1 到 n 的最短路径,如果到达不了的话,请输出 -1。

示例1

输入

复制4 5 1 1 0 1 0 1 2 10 2 3 10 3 1 15 1 4 60 3 4 30

4 5 1
1
0
1
0
1 2 10
2 3 10
3 1 15
1 4 60
3 4 30

输出

复制60

60

先上WA的代码(90%通过率)

#include<bits/stdc++.h>
using namespace std;
const int maxn = 810;
vector<int>defense(maxn), dis(maxn, INT_MAX), pre(maxn, -1), vis(maxn);
#define endl '\n'
int n, m, k, A, B, len;
struct edge
{
    int form, to, dis;
    edge(int a, int b, int c) : form(a), to(b), dis(c) {};
};
vector<edge>e[maxn];
struct q_node
{
    int id, dis;
    q_node(int a, int b) : id(a), dis(b) {};
    bool operator < (const q_node& s)const
    {
        return dis > s.dis;
    }
};
void dijkstra()
{
    dis[1] = 0;
    int T = 0;// defense[1];
    priority_queue<q_node>Q;
    Q.emplace(1, dis[1]);
    while (!Q.empty())
    {
        auto x = Q.top();
        Q.pop();
        if (T == k && defense[x.id] == 1)vis[x.id] = true;
        if (vis[x.id])continue;
        vis[x.id] = true;
        T += defense[x.id];
        for (int i = 0; i < e[x.id].size(); i++)
        {
            auto y = e[x.id][i];
         //   if (T == k && defense[y.to] == 1 && y.to != n)vis[y.to] = true;
            if (vis[y.to])continue;
            if (dis[y.to] > dis[x.id] + y.dis)
            {
                dis[y.to] = dis[x.id] + y.dis;
                pre[y.to] = x.id;
                Q.emplace(y.to, dis[y.to]);
            }
        }
    }
}
int main()
{
    cin.tie(0)->sync_with_stdio(false);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
        cin >> defense[i];
    while (m--)
    {
        cin >> A >> B >> len;
        e[A].emplace_back(A, B, len);
        e[B].emplace_back(B, A, len);
    }
    dijkstra();
    dis[n] == INT_MAX ? cout << "-1" << endl : cout << dis[n] << endl;
    return 0;
}

进行更改后通过的代码 

#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int maxn = 810;
vector<int>defense(maxn), dis(maxn, INT_MAX), pre(maxn, -1), vis(maxn);
#define endl '\n'
int n, m, k, A, B, len;
struct edge
{
    int form, to, dis;
    edge(int a, int b, int c) : form(a), to(b), dis(c) {};
};
vector<edge>e[maxn];
struct q_node
{
    int id, dis, T;
    q_node(int a, int b, int c) : id(a), dis(b), T(c) {};
    bool operator < (const q_node& s)const
    {
        return dis > s.dis;
    }
};
void dijkstra()
{
    dis[1] = 0;
    priority_queue<q_node>Q;
    Q.emplace(1, dis[1], defense[1]);
    if(!k && defense[1])return;
    while (!Q.empty())
    {
        auto x = Q.top();
        Q.pop();
        if (vis[x.id])continue;
        vis[x.id] = true;
        for (int i = 0; i < e[x.id].size(); i++)
        {
            auto y = e[x.id][i];
            if (vis[y.to])continue;
            if (dis[y.to] > dis[x.id] + y.dis && (x.T + defense[y.to] <= k || y.to == n))
            {
                dis[y.to] = dis[x.id] + y.dis;
                pre[y.to] = x.id;
                //defense[y.to] += x.T; 
                Q.emplace(y.to, dis[y.to], x.T + defense[y.to]);
            }
        }
    }
}
int main()
{
    cin.tie(0)->sync_with_stdio(false);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
        cin >> defense[i];
    while (m--)
    {
        cin >> A >> B >> len;
        e[A].emplace_back(A, B, len);
        e[B].emplace_back(B, A, len);
    }
    dijkstra();
    dis[n] == INT_MAX ? cout << "-1" << endl : cout << dis[n] << endl;
    return 0;
}

首先对于结构体的解释

struct q_node
{
    int id, dis, T;
    q_node(int a, int b, int c) : id(a), dis(b), T(c) {};
    bool operator < (const q_node& s)const
    {
        return dis > s.dis;
    }
};

id是城镇编号,dis为使用这条边将id纳入最短路花费的距离,T表示使用这条边要战斗的次数

其中   defense[y.to] += x.T; 一定不能使用(对于这题而言如果更改defense只能通过90%原因后面解释)

defense用于记录该城镇是否有敌人防御

为什么defense不能更改反而要在结构体中新添一个变量T ?

原因:每一个点可能会经过多次松弛,可能对于该次松弛,该点无法纳入最短路,如果我们这时候将defense进行更改相当于直接否认该点能纳入最短路,但是可能在后面的松弛中该点又被允许纳入选择中.因此对于同一个点,起点到该的需要战斗的次数受之前的选择决定,每一次对于战斗的状态的不固定的,那我们就得根据边的选择来记录当前到该城镇所需战斗的状态


http://lihuaxi.xjx100.cn/news/1175490.html

相关文章

如何用海外代理辅助对接 ChatGPT

许多朋友问我有没有好用的海外代理。说实话&#xff0c;真的好用的并不多。 最近我了解到了一家还不错的海外代理&#xff0c;叫做 IPIDEA&#xff0c;我已经使用了一段时间了&#xff0c;觉得质量挺不错。 你可能知道&#xff0c;我最近在进行一些 ChatGPT 相关的研究&#xf…

平衡二叉树的插入,删除以及平衡调整。

一&#xff0c;平衡二叉树插入失衡情况及解决方案 由于各种的插入导致的不平衡&#xff0c;每次调整都是最小不平衡子树。 LL&#xff1a;由于在结点A的 左孩子的左子树 插入结点导致失衡。 右单旋&#xff1a;①将A的 左孩子B 向右上旋转 代替A成为根节点       ②将A结…

springboot+vue广场舞团系统(java项目源码+文档)

风定落花生&#xff0c;歌声逐流水&#xff0c;大家好我是风歌&#xff0c;混迹在java圈的辛苦码农。今天要和大家聊的是一款基于springboot的广场团舞系统。项目源码以及部署相关请联系风歌&#xff0c;文末附上联系信息 。 &#x1f495;&#x1f495;作者&#xff1a;风歌&a…

带你深入了解RecyclerView的缓存机制

RecyclerView是Android中常用的列表显示控件&#xff0c;它具有强大的灵活性和性能优势。其中&#xff0c;RecyclerView的缓存机制是其实现高效滚动和快速显示大量数据的重要因素之一。在本文中&#xff0c;我们将详细解析RecyclerView的缓存机制&#xff0c;并附上相关示例代码…

springboot+vue大学生租房系统(java项目源码+文档)

风定落花生&#xff0c;歌声逐流水&#xff0c;大家好我是风歌&#xff0c;混迹在java圈的辛苦码农。今天要和大家聊的是一款基于springboot的大学生租房系统。项目源码以及部署相关请联系风歌&#xff0c;文末附上联系信息 。 &#x1f495;&#x1f495;作者&#xff1a;风歌…

挂耳式耳机哪个牌子好?这次推荐准没错!

在校园里&#xff0c;上网课、复习考证、刷视频……耳机总是我的第一选择&#xff0c;既不会打扰别人又能有效学习&#xff0c;普通的入耳式耳机戴久了总是会耳道痛&#xff0c;甚至出现耳道发炎问题&#xff0c;耳机也总是很难清洁。但是生活中我又离不开耳机&#xff0c;所以…

C#开发的OpenRA游戏之基地工程车移动5

前面已经分析到寻路算法,这个是RPG游戏的必经之路,因为角色的移动都是根据鼠标点击来实现,而点击的鼠标位置就是角色将要到达的目标位置。角色所在位置与目标位置就有一定的距离,并且之间有各种地形,以及各种游戏角色动态地阻挡。因此角色所在位置与目标位置之间,就需要采…

chatgpt赋能python:Python文件名字替换-优化SEO的必备技巧

Python文件名字替换-优化SEO的必备技巧 作为一名有10年Python编程经验的工程师&#xff0c;我深知文件名字替换在优化搜索引擎排名中占有重要的地位。本文将介绍如何使用Python进行文件名字替换以优化SEO&#xff0c;旨在为广大编程初学者提供有益的参考和指导。 什么是文件名…