「CSP-J T4求助（骗分算法出问题了，悬赏一关）」

CSP-J T4求助（骗分算法出问题了，悬赏一关）

板块学术版
楼主godmoo
当前回复13
已保存回复13
发布时间2023/10/22 07:39
上次更新2023/11/2 12:02:40

被骇客银狼阻止的越权访问保存失败

CSP-J T4求助（骗分算法出问题了，悬赏一关）

godmoo楼主2023/10/22 07:39

测试点编号	$n \leq$	$m \leq$	$k \leq$	特殊性质
$1 \sim 2$	$10$	$15$	$100$	$a _ i = 0$
$3 \sim 5$	$10$	$15$	$100$	无
$6 \sim 7$	$10 ^ 4$	$2 \times 10 ^ 4$	$1$	$a _ i = 0$
$8 \sim 10$	$10 ^ 4$	$2 \times 10 ^ 4$	$1$	无
$11 \sim 13$	$10 ^ 4$	$2 \times 10 ^ 4$	$100$	$a _ i = 0$
$14 \sim 15$	$10 ^ 4$	$2 \times 10 ^ 4$	$100$	$u _ i \leq v _ i$
$16 \sim 20$	$10 ^ 4$	$2 \times 10 ^ 4$	$100$	无

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
const int M=2e4+5; 
int n,m,k,flag,cnt,head[N];
struct Edge{int to,nxt;}edge[M];
void add(int u,int v){
	edge[++cnt]={v,head[u]};
	head[u]=cnt;
}
struct Node{
	int u,dis;
	bool operator <(const Node tmp) const{return dis>tmp.dis;}
};
priority_queue<Node> q;
int dijkstra(){
	int dis[N],vis[N];
	memset(dis,0x7f,sizeof dis),dis[1]=0;
	memset(vis,0,sizeof vis);
	q.push({1,0});
	while(!q.empty()){
		int u=q.top().u;
		q.pop();
		for(int i=head[u];i;i=edge[i].nxt){
			int v=edge[i].to;
			if(dis[v]>dis[u]+1){
				dis[v]=dis[u]+1;
				if(!vis[v]) vis[v]=1,q.push({v,dis[v]});
			}
		}
	}
	return dis[n];
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1,u,v,a;i<=m;i++){
		scanf("%d%d%d",&u,&v,&a);
		add(u,v);
		if(a!=0) flag=1;
	}
	int ans=dijkstra();
	if(ans==0x7f7f7f7f) printf("-1");
	else if(flag) printf("%d",n*k/5*2);
	else{
		if(ans%k) ans+=k-(ans%k);
		printf("%d",ans);
	}
	return 0;
}

我的骗分算法：暴力跑 $dijkstra$ , 再往上找 $k$ 倍，这样应该能 A 所有 $a _ i = 0$ 的点，期望得分 $35$ , 实际得分 $15$ ，求原因
评测记录

2023/10/22 07:39