### 亲,~~86是哪来的,是84吧,~~ 我也是84,最后一个点WA, _~~**来蹭个车**~~_
------------
我用的是kruskal+dijstra做的
```cpp
#include <bits/stdc++.h>
using namespace std;
int f[110],n,m,s,t,num=0,head[6010],vis[6010],dis[6010],now=0,ans=-1;
struct road{
int from,to,dis;
bool operator<(const road &r)const{
return dis<r.dis;
}
}r[6010];
struct Edge{
int to,next,d;
}edge[6010];
void addEdge(int from,int to,int dis){
num++;
edge[num].to=to;
edge[num].d=dis;
edge[num].next=head[from];
head[from]=num;
}
int find(int x){
int r=x;
while(r!=f[r]){
r=f[r];
}
while(x!=f[x]){
x=f[x];
f[x]=r;
}
return r;
}
void uni(int x,int y){
int fx=find(x);
f[fx]=find(y);
}
priority_queue<pair<int,int> >q;
int main(){
cin>>n>>m>>s>>t;
int x,y,z;
for(int i=1;i<=m;i++){
cin>>x>>y>>z;
addEdge(x,y,z);
addEdge(y,x,z);
}
for(int i=1;i<=m;i++){
cin>>r[i].from>>r[i].to>>r[i].dis;
}
sort(r+1,r+m+1);
for(int i=1;i<=m;i++){
if(find(r[i].from)!=find(r[i].to)){
uni(r[i].from,r[i].to);
now++;
addEdge(r[i].from,r[i].to,r[i].dis);
addEdge(r[i].to,r[i].from,r[i].dis);
}
if(now==n-1){
break;
}
}
for(int i=1;i<=n;i++)
dis[i]=1e9;
dis[s]=0;
q.push(make_pair(0,s));
while(q.size()){
int tmp=q.top().second;
q.pop();
if(vis[tmp])
continue;
vis[tmp]=1;
for(int i=head[tmp];i;i=edge[i].next){
int k=edge[i].to,d=edge[i].d;
if(dis[k]>dis[tmp]+d){
dis[k]=dis[tmp]+d;
q.push(make_pair(-dis[k],k));
}
}
}
for(int i=s+1;i<=t;i++){
ans=max(ans,dis[i]-dis[head[i]]);
}
cout<<ans;
}
```
by NianFeng @ 2022-05-29 14:18:54
蹭车+1
by xuhanxi_dada117 @ 2022-07-24 17:10:55
好了注意有的优惠是无良优惠,
不优惠更好
by xuhanxi_dada117 @ 2022-07-24 17:12:44