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进行更改相当于直接否认该点能纳入最短路,但是可能在后面的松弛中该点又被允许纳入选择中.因此对于同一个点,起点到该的需要战斗的次数受之前的选择决定,每一次对于战斗的状态的不固定的,那我们就得根据边的选择来记录当前到该城镇所需战斗的状态
