改了好多次,总有两个点RE
附上我的Code:
#include<bits/stdc++.h>
using namespace std;
const int N=2510,M=6950;
int n,m,s,t,tot=0,head[N],nex[M],d[N],w[M],ver[M];
bool vis[N];
priority_queue < pair< int ,int > >qu;
void add(int u,int v,int z)
{ tot++;
nex[tot]=head[u];
ver[tot]=v;
w[tot]=z;
head[u]=tot;
}
void path()
{ memset(d,0x3f,sizeof(d));
memset(vis,0,sizeof(vis));
d[s]=0;
qu.push(make_pair(0,s));
while(qu.size())
{ int x=qu.top().second;
qu.pop();
if(vis[x])
{ continue ;
}
vis[x]=1;
for(int i=head[x];i;i=nex[i])
{ int y=ver[i],z=w[i];
if(d[y]>d[x]+z)
{ d[y]=d[x]+z;
qu.push(make_pair(-d[y],y));
}
}
}
return ;
}
int main()
{ int x,y,z;
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++)
{ cin>>x>>y>>z;
add(x,y,z);
add(y,x,z);
}
path();
cout<<d[t];
cout<<" ";
cout<<endl;
return 0 ;
}