0pts | 40pts 求调
查看原帖
0pts | 40pts 求调
769006
crzcqh楼主2024/8/12 10:41

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。

2024/8/12 10:41
加载中...