本文共 1585 字，大约阅读时间需要 5 分钟。

观察表达式$\sum w_i-max+min$

首先$\sum w_i$就是普通的最短路

所以应该往最短路的方向考虑…然后就不知道了…

其实等价于,有一次把边权置零的机会,有一次把边权置两倍的机会,而且需要全部用掉

为什么可以这样等价??

这样跑分层图,用这样的两次机会,一定会分别用在边权最大和最小的边上

因为这是最有利于最小化距离的方式,所以是没问题的

那么有四种状态

$0$表示没使用一次机会,$1$表示用了边权为$0$的机会

$2$表示用了边权两倍的机会,$3$表示用完了两次机会

值得一提的是$0$可以使用正常的边权转移到$3$去

这样可以有效避免当$1$到$i$经过的边等于$1$的情况,因为$min$和$max$需要两次转移

#include 
   
     using namespace std;#define int long longconst int inf = 1e18;const int maxn = 4e6+10;struct edge{
   	int to,nxt,w;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v,int w) {
    d[++cnt] = (edge){
   v,head[u],w},head[u] = cnt; }typedef pair
    
     p;priority_queue
     
      
,greater
      
 >q;int vis[maxn],n,m,dis[maxn];void dijstra(int s) {
   	for(int i=1;i<=4*n;i++)	dis[i] = inf, vis[i] = 0;	dis[s] = 0;	q.push( p(0,s) );	while( !q.empty() )	{
   		int u = q.top().second; q.pop();		if( vis[u] )	continue;		vis[u] = 1;		for(int i=head[u];i;i=d[i].nxt )		{
   			int v = d[i].to;			if( dis[v]>dis[u]+d[i].w )			{
   				dis[v] = dis[u]+d[i].w;				if( !vis[v] )	q.push( p(dis[v],v) );			}		}	}}//0是什么都没有//1是免费,2是双倍,3是全部 signed main(){
   	cin >> n >> m;	for(int i=1;i<=m;i++)	{
   		int l,r,w; scanf("%lld%lld%lld",&l,&r,&w);		for(int j=0;j<=3;j++)			add(l+j*n,r+j*n,w),add(r+j*n,l+j*n,w);			add(l,r+n,0); add(r,l+n,0);		add(l,r+2*n,2*w); add(r,l+2*n,2*w);		add(l,r+3*n,w); add(r,l+3*n,w);				add(l+n,r+3*n,2*w); add(r+n,l+3*n,2*w);		add(l+2*n,r+3*n,0 ); add(r+2*n,l+3*n,0 );	}	dijstra(1);	for(int i=2;i<=n;i++)	cout << dis[i+3*n] << " ";	return 0;}
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/112758811 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！