刚开始拿到这题的时候我直接懵逼了:字典序是啥玩意,这东西貌似很高大尚的亚子
然而,认真读了一下题后,我发现其实这道题跟我做过的某些题很像
比如: timeline
可能大佬们会说,貌似这题跟timeline没有一毛钱关系啊...
其实,这道题可以理解为,算出每个点到1的最短距离,然后计算每个点对点1连线最大能减少的距离
那么问题来了,你怎么知道这个点跟1连线后有几头牛改变了路径?
这里就得到了这题的核心思想:我们发现,奶牛只有在走原先路径时遇到捷径才会去.他们不会刻意走去捷径.
于是,这题就可以转化为,求出(这个点到点1的距离-连边的距离)*经过这点的奶牛的数量的和
说人话
求出每个点的子树的数量*从这个节点用捷径能节省的距离
这样会好理解点吗?
好下面正式开始解题:
1.求最短距离
模板题,从点1用 (dijkstra) 求最短距离,这个不详细讲
2.求子树
敲重点:
这里就到了跟timeline相似的地方了.我们发现,如果一个点的子树还没有处理完,那么我们无法用这个点去更新他的父节点(如果无法理解可以看我的timeline的解法(timeline题解).
所以,对于每个节点,我们将其父节点设为不可更新.然后,我们将所有可以更新的节点放进 (queue) 里. 每当一个子节点要更新父节点的时候,我们将父节点的子叶数量-1.当一个父节点没有子叶了,那么他将会转化为一个子节点,然后我们就可以拿它继续更新他的父节点了
for (pp v : adj[qf]){
if (dist[v.f]==dist[qf]-v.s){
constrain[v.f]--;//父节点子叶--
pos[v.f]+=pos[qf];
if (constrain[v.f]==0) q.push(v.f);//如果父节点没有子叶了
break;
}
}
3.答案
答案之前其实已经提到过,就是每个点的子叶数量*用捷径所能减少的距离
for (long long i=n;i>=1;i--){
ans = max(ans,pos[i]*(dist[i]-k));
}
4.字典序的求法
这里是很多链式前向星的大佬卡住的地方.正常的方法是用fa存.然而,我们发现,如果用vector存图,我们可以将去的点排序,然后将遇到的第一个父节点(也就是距离最短的点)扔进队列.
这里我写的spfa没写dij,但是想法是一样的
又到了具体代码的时间了:
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
const long long MAXN = 1e5+5;
#define pp pair<long long,long long>
#define f first
#define s second
long long dist[MAXN], n,m,k, pos[MAXN],constrain[MAXN], ans= 0 ;
vector<pp> adj[MAXN];
bool inq[MAXN],vis[MAXN];
inline void spfa(long long source){
memset(dist,0x3f3f3f3f,sizeof(dist));
dist[source] = 0;
queue<long long> q;
q.push(source);
while(!q.empty()){
long long qf = q.front();q.pop();
inq[qf] = false;
for (pp v : adj[qf]){
if (dist[v.f]>dist[qf]+v.s){
dist[v.f] = dist[qf]+v.s;
if (!inq[v.f]) inq[v.f] = true,q.push(v.f);
}
}
}
}//板子,不解释
inline void dfs(long long source){
for (pp v : adj[source]){
if (dist[v.f]==dist[source]-v.s){//如果某个点到点1的距离-他去父节点的距离==父节点到点1的距离
constrain[v.f]++;
break;//已经改过,break能保证字典序最小
}
}
}
inline void bfs(){
queue<int> q;
for (int i=1;i<=n;i++) if (!constrain[i]) q.push(i);//如果是子叶
while(!q.empty()){
int qf = q.front();q.pop();
for (pp v : adj[qf]){
if (dist[v.f]==dist[qf]-v.s){//同上
constrain[v.f]--;//子叶-1
pos[v.f]+=pos[qf];//子叶数量相加
if (constrain[v.f]==0) q.push(v.f);//如果父节点变成了子叶
break;//字典序
}
}
}
}
long long a,b,c;
int main(){
cin >> n >> m >> k;
for (long long i=1;i<=n;i++) cin >> pos[i];
for (long long i=0;i<m;i++){
cin >> a >> b >> c;
adj[a].push_back(make_pair(b,c));
adj[b].push_back(make_pair(a,c));
//vector的建边方式
}
for (long long i=1;i<=n;i++) sort(adj[i].begin(),adj[i].end());//排序保证字典序
spfa(1);//板子
for (long long i=1;i<=n;i++) dfs(i);//这名字...其实不是dfs
bfs();
for (long long i=n;i>=1;i--) ans = max(ans,pos[i]*(dist[i]-k));//求答案
cout << ans;
}