Rinne Loves Graph

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

输出

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