题目传送门

P5201 [USACO19JAN]Shortcut G

思路分析

看题解里的大佬都是用最短路树求解的，没学过最短路树的我看的一脸蒙。这里给出另一种解法（常数略大，但能跑过）。
首先，题目要求字典序最小的最短路路径。先不管字典序，先在常规的最短路算法中求出最短路径。这个比较好求，只要在更新最短路的同时中加入这样一句话：

q[y]=x;

其中 $x$ 表示当前节点，$y$ 表示更新的节点。这样一句短短的代码，可以记录每一个当前节点的前驱节点，而前驱节点的前驱节点肯定是被记录过的，所以可以用一个递归函数输出路径：

void print(int x)
{
	cout<<x<<" ";
	if(q[x]==0)return ;
	print(q[x]);
}

到了这一步以后，将记录节点的顺序改为最小字典序的方法就很简单了，只需要把原本代码中的松弛操作：

if(dis[y]>dis[x]+e[i].w)

改为：

if(dis[y]>dis[x]+e[i].w || (dis[y]==dis[x]+e[i].w && x<q[y]))

即可。
显而易见的是，每一个点在到原点的路径中，一定会经过某一个节点（包括自身）。如果此时将近路连到这个节点上，那么所有经过这个点的牛就都不会走原本的路，而是走这条近路。拿题目举个栗子：
$2$ 号节点的路径为：$2\to1$
$4$ 号节点的路径为：$4\to2\to1$
而 $2$ 号节点有 $2$ 头牛，$4$ 号节点有 $4$ 头牛。所以如果近路接到 $2$ 号节点，那么最后一共会有 $6$ 头牛走近路。
而 $2$ 号节点到原点的最短路长度为 $5$，近路的长度为 $2$，所以一共减少消耗的时间为 $(5-2)\times6=18$
同样：
$3$ 号节点的路径为：$3\to1$
$5$ 号节点的路径为：$5\to3\to1$
而 $3$ 号节点有 $3$ 头牛，$5$ 号节点有 $5$ 头牛。所以如果近路接到 $3$ 号节点，那么最后一共会有 $8$ 头牛走近路。
而 $3$ 号节点到原点的最短路长度为 $3$，近路的长度为 $2$，所以一共减少消耗的时间为 $(3-2)\times8=8$

所以，只需要在每一个点的路径上加上这个点本身的点权，再枚举每个点，计算连边到这个点能够减少的时间，取最大值就好了。

代码

#include<bits/stdc++.h>
#define inf 0x7f7f7f7f
using namespace std;
struct E{
	int to,next,w;
}e[111111];
int e_num,p[111111];
void e_add(int x,int y,int w)//邻接表存图 
{
	e[++e_num].to=y;
	e[e_num].w=w;
	e[e_num].next=p[x];
	p[x]=e_num; 
}
int n,m,t;
long long c[111111],a[111111];//注意开long long 
long long dis[111111];
int mark[111111];
int q[111111];
void SPFA()
{
	for(int i=1;i<=n;i++)dis[i]=inf;
	dis[1]=0;
	mark[1]=1;
	queue<int>que;
	que.push(1);
	while(!que.empty())
	{
		int x=que.front();
		mark[x]=0;
		que.pop();
		for(int i=p[x];i;i=e[i].next)
		{
			int y=e[i].to;
			if(dis[y]>dis[x]+e[i].w || (dis[y]==dis[x]+e[i].w && x<q[y]))//后面这部分是保持字典序的关键 
			{
				q[y]=x;//保存前驱节点 
				dis[y]=dis[x]+e[i].w;
				if(!mark[y])
				{
					mark[y]=1;
					que.push(y);
				}
			}
		}
	}
}
void print(int x,int c)
{
	a[x]+=c;
	if(q[x]==0)return ;
	print(q[x],c);
}
int main()
{
	scanf("%d%d%d",&n,&m,&t);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",c+i);
	}
	for(int i=1;i<=m;i++)
	{
		int x,y,w;
		scanf("%d%d%d",&x,&y,&w);
		e_add(x,y,w);//双向建边 
		e_add(y,x,w);
	}
	SPFA();//考试的时候如果没有负权边不建议用SPFA（它死了）...
	for(int i=1;i<=n;i++)
		print(i,c[i]);//累加牛的数量 
	long long ans=0;//不开____见祖宗 
	for(int i=1;i<=n;i++)
		ans=max(ans,(dis[i]-t)*a[i]);//枚举 
	cout<<ans;
	return 0;
}