一、算法分析
首先想朴素的方法，存图，先跑一遍最短路，然后枚举扩大二倍的边，然后再跑最短路。然后优化，易证扩大的边必然是原最短路的边，所以要记录原最短路的边，记录方式是写一个pre数组，这样从后往前扫一遍就行了。但是注意两个难点，一是如何在链式前向星中扩大边权，我采用的方式是，用邻接矩阵来存某两个点a到b的边在前向星数组中的w的编号。二是要注意，只有第一次跑单源最短路的时候，要记录pre数组，之后的都不能改pre数组了，否则可能会发生死循环，我采用的解决方法是给dijkstra函数加一个参数用来标记是否是第一次跑即可。
二、代码及注释
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#define x first
#define y second
using namespace std
;
typedef pair
<int,int> PII
;
const int inf
=0x3f3f3f3f;
const int N
=150;
const int M
=10050;
int G
[N
][N
];
int dist
[N
];
int st
[N
];
int n
,m
;
int pre
[N
];
int h
[N
],e
[M
],ne
[M
],w
[M
],idx
;
void add(int a
,int b
,int c
){
G
[a
][b
]=idx
;
e
[idx
]=b
,w
[idx
]=c
,ne
[idx
]=h
[a
],h
[a
]=idx
++;
}
void dijkstra(bool firstly
){
memset(dist
,0x3f,sizeof(dist
));
memset(st
,0,sizeof(st
));
priority_queue
<PII
,vector
<PII
> ,greater
<PII
> > q
;
dist
[1]=0;
q
.push({0,1});
while(q
.size()){
auto t
=q
.top();
int ver
=t
.y
;
q
.pop();
if(st
[ver
]) continue;
st
[ver
]=1;
for(int i
=h
[ver
];~i
;i
=ne
[i
]){
int j
=e
[i
];
if(dist
[j
]>dist
[ver
]+w
[i
]){
dist
[j
]=dist
[ver
]+w
[i
];
if(firstly
) pre
[j
]=ver
;
q
.push({dist
[j
],j
});
}
}
}
}
int main(){
memset(h
,-1,sizeof(h
));
cin
>>n
>>m
;
for(int i
=0;i
<m
;i
++){
int a
,b
,c
;
cin
>>a
>>b
>>c
;
add(a
,b
,c
);
add(b
,a
,c
);
}
dijkstra(1);
int ans1
=dist
[n
];
int ans2
=0;
int end
=n
;
while(end
!=1){
int a
=end
,b
=pre
[end
];
w
[G
[a
][b
]]=w
[G
[b
][a
]]=2*w
[G
[a
][b
]];
dijkstra(0);
ans2
=max(ans2
,dist
[n
]);
w
[G
[a
][b
]]=w
[G
[b
][a
]]=w
[G
[a
][b
]]/2;
end
=pre
[end
];
}
cout
<<ans2
-ans1
;
return 0;
}
