0pts 代码:
#include<bits/stdc++.h>
#define N 5005
#define M 100005
#define ll long long
#define reg register
using namespace std;
ll n,m,u,v,w;
ll dis1[N],dis2[N],vis[N];
vector<pair<ll,ll> > edge[N];
priority_queue<ll> q;
inline ll read(){
ll f=1,s=0;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<3)+(s<<1)+ch-48;
ch=getchar();
}
return f*s;
}
void add(ll u,ll v,ll w){
edge[u].push_back(make_pair(v,w));
}
void dijkstra(ll x){
memset(dis1,0x3f,sizeof dis1);
memset(dis2,0x3f,sizeof dis2);
memset(vis,0,sizeof vis);
dis1[x]=0,dis2[x]=0,q.push(x);
while(!q.empty()){
u=q.top();
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(auto i : edge[u]){
v=i.first,w=i.second;
if(dis1[v]>dis1[u]+w){
dis2[v]=dis1[v];
dis1[v]=dis1[u]+w;
q.push(v);
}
if(dis2[v]>dis1[u]+w&&dis1[u]+w>dis1[v]){
dis2[v]=dis1[u]+w;
q.push(v);
}
if(dis2[v]>dis2[u]+w){
dis2[v]=dis2[u]+w;
q.push(v);
}
}
}
}
int main(){
n=read(),m=read();
for(reg ll i=1;i<=m;i++){
u=read(),v=read(),w=read();
add(u,v,w),add(v,u,w);
}
dijkstra(1);
cout<<dis2[n];
return 0;
}
我把dijkstra中的if(dis2[v]>dis2[u]+w) 注释掉后获得了 40pts。