RT,错误信息:
Runtime Error.
Received signal 11: Segmentation fault with invalid memory reference.
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct s1{
ll i,l;
};
vector<s1> a[100001];
bool cmp(s1 num1,s1 num2){
return num1.l<num2.l;
}
struct s2{
ll x,y,l;
}b[200001];
ll last[800001];
struct s3{
ll t,to,l;
}nxet[2000001];
ll cd=0;
void lj(ll x,ll y,ll l){
nxet[++cd].t=last[x];
nxet[cd].to=y;
nxet[cd].l=l;
last[x]=cd;
}
ll dis[800001];
bool vis[800001];
struct s4{
ll x,l;
}h[2000001];
ll len=1;
bool f(s4 num1,s4 num2){
return num1.l>num2.l;
}
void dijkstra(ll s){
memset(dis,0x3f,sizeof(dis));
dis[s]=0;
h[0]={s,0};
while(len){
ll x=h[0].x;
pop_heap(h,h+len,f);
len--;
if(vis[x])
continue;
vis[x]=1;
for(ll j=last[x];j;j=nxet[j].t){
ll y=nxet[j].to;
if(dis[y]>dis[x]+nxet[j].l){
dis[y]=dis[x]+nxet[j].l;
h[len].x=y;
h[len++].l=dis[y];
push_heap(h,h+len,f);
}
}
}
}
int main(){
ll n,m;
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=m;i++){
scanf("%lld%lld%lld",&b[i].x,&b[i].y,&b[i].l);
if(b[i].x>b[i].y)
b[i].x^=b[i].y^=b[i].x^=b[i].y;
a[b[i].x].push_back({i,b[i].l});
a[b[i].y].push_back({i,b[i].l});
}
for(ll i=1;i<=n;i++){
sort(a[i].begin(),a[i].end(),cmp);
ll x,y;
if(b[a[i][0].i].x==i){
x=4*a[i][0].i-3;
y=4*a[i][0].i-2;
} else {
x=4*a[i][0].i-1;
y=4*a[i][0].i;
}
lj(x,y,a[i][0].l);
lj(y,x,0);
ll y0=y;
for(ll j=1;j<a[i].size();j++){
if(b[a[i][j].i].x==i){
x=4*a[i][j].i-3;
y=4*a[i][j].i-2;
} else {
x=4*a[i][j].i-1;
y=4*a[i][j].i;
}
lj(y0,y,a[i][j].l-a[i][j-1].l);
lj(y,y0,0);
lj(x,y,a[i][j].l);
lj(y,x,0);
y0=y;
}
}
for(ll i=1;i<=m;i++){
lj(4*i-2,4*i-1,0);
lj(4*i,4*i-3,0);
}
dijkstra(4*a[1][0].i-3);
ll ans=0x3f3f3f3f3f3f3f3f;
for(ll i=0;i<a[n].size();i++)
ans=min(ans,dis[4*a[n][i].i]);
printf("%lld",ans);
return 0;
}